❶ matlab實現floyd演算法 已知距離矩陣和權值矩陣 求最短路徑
希望可以幫到你。
function [D,path]=floyd(a)
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k)
end
end
end
end
function [L,R]=router(D,path,s,t)
L=zeros(0,0);
R=s;
while 1
if s==t
L=fliplr(L);
L=[0,L];
return
end
L=[L,D(s,t)];
R=[R,path(s,t)];
s=path(s,t);
end
❷ 求Matlab Floyd演算法代碼，要求能計算矩陣任意兩節點的最短距離，得到所有可能的路徑
去codesoso和pudn看看吧，哪裡應該有你想要的東西。。。
❸ 圖無負環，最短路徑演算法（Floyd-Warshall，Bellman-Ford演算法，MATLAB實現）輸出環路，是什麼原因
§1 Dijkstra演算法
Dijkstra演算法思想
Dijkstra演算法思想為：設G=(V,E)是一個帶權有向圖（無向可以轉化為雙向有向），把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
Dijkstra演算法具體步驟
（1）初始時，S只包含源點，即S＝{v}，v的距離dist[v]為0。U包含除v外的其他頂點，U中頂點u距離dis[u]為邊上的權值（若v與u有邊） ）或∞（若u不是v的出邊鄰接點即沒有邊<v,u>）。
（2）從U中選取一個距離v(dist[k])最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u∈ U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值的頂點k的距離加上邊上的權(即如果dist[k]+w[k,u]<dist[u]，那麼把dist[u]更新成更短的距離dist[k]+w[k,u])。
（4）重復步驟（2）和（3）直到所有頂點都包含在S中(要循環n-1次)。
╝①
Dijkstra演算法實現
╔
直接實現
最簡單的實現方法就是，在每次循環中，再用一個循環找距離最短的點，然後用任意的方法更新與其相鄰的邊，時間復雜度顯然為O(n²)
對於空間復雜度：如果只要求出距離，只要n的附加空間保存距離就可以了（距離小於當前距離的是已訪問的節點，對於距離相等的情況可以比較編號或是特殊處理一下）。如果要求出路徑則需要另外V的空間保存前一個節點，總共需要2n的空間。
╝②
╔
Cpp代碼
/*********************************
* 最短路徑---Dijkstra演算法實現
* HDU：2544
* BLOG:www.cnblogs.com/newwy
* AUTHOR:Wang Yong
**********************************/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
int dijkstra (int mat[][MAX],int n, int s,int f)
{
int dis[MAX];
int mark[MAX];//記錄被選中的結點
int i,j,k = 0;
for(i = 0 ; i < n ; i++)//初始化所有結點，每個結點都沒有被選中
mark[i] = 0;
for(i = 0 ; i < n ; i++)//將每個結點到start結點weight記錄為當前distance
{
dis[i] = mat[s][i];
//path[i] = s;
}
mark[s] = 1;//start結點被選中
//path[s] = 0;
dis[s] = 0;//將start結點的的距離設置為0
int min ;//設置最短的距離。
for(i = 1 ; i < n; i++)
{
min = INF;
for(j = 0 ; j < n;j++)
{
if(mark[j] == 0 && dis[j] < min)//未被選中的結點中，距離最短的被選中
{
min = dis[j] ;
k = j;
}
}
mark[k] = 1;//標記為被選中
for(j = 0 ; j < n ; j++)
{
if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//修改剩餘結點的最短距離
{
dis[j] = dis[k] + mat[k][j];
}
}
}
return dis[f];
}
int mat[MAX][MAX];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m))
{
int a,b,dis;
if(n == 0 || m == 0)
break;
int i,j;
for(i = 0 ; i < n;i++)
for(j = 0 ; j < n; j++)
mat[i][j] = INF;
for(i = 0 ; i < m ;i++)
{
scanf("%d %d %d",&a,&b,&dis);
--a,--b;
if(dis < mat[a][b] || dis < mat[b][a])
mat[a][b] = mat[b][a] = dis;
}
int ans = dijkstra(mat,n,0,n-1);
printf("%d\n",ans);
}
}
╝⑤
╔
二叉堆實現
使用二叉堆(Binary Heap)來保存沒有擴展過的點的距離並維護其最小值，並在訪問每條邊的時候更新，可以把時間復雜度變成O((V+E)logV)。
當邊數遠小於點數的平方時，這種演算法相對來說有很好的效果。但是當E=O(V2)時（有時候表現為不限制邊的條數），用二叉堆的優化反倒會更慢。因為此時的復雜度是O(V+V*2logV)，小於不用堆的實現的O(n²)的復雜度。
另外此時要用鄰接表保存邊，使得擴展邊的總復雜度為O(E)，否則復雜度不會減小。
空間復雜度：這種演算法需要一個二叉堆，及其反向指針，另外還要保存距離，所以所用空間為3V。如果保存路徑則為4V。
具體思路：先將所有的點插入堆，並將值賦為極大值(maxint/maxlongint)，將原點賦值為0，通過鬆弛技術（relax）進行更新以及設定為擴展。
╝②
╔
C代碼
int GraphDijk(struct Graph *g, int root, int *parent, int *distance)
{
// 將除根結點之外的點都放入堆中，設置所有鍵為INFINITY
// 遍歷根結點發出的邊，將其最短路徑設為相應權值，並維持堆性質
// RemoveTop，此結點已經取最短路徑，如果為INFINITY，則終止演算法
// 否則，將其狀態設為已標記，並設為根結點
// loop back
parent[root] = root;
int reflection[g->V];
int heap_real[g->V - 1];
for (int i=0,j=0; i < g->V; i++) {
if (i == root) {
distance[i] = 0;
} else {
distance[i] = INFINITY;
heap_real[j++] = i;
reflection[i] = j;
}
}
struct Edge *e;
struct list_t *iter;
int *heap = heap_real - 1;
int base = 0; /* euqal to distance[root] */
int size = g->V - 1;
int length;
do {
iter = list_next(&(g->vertices + root)->link);
for (; iter; iter = list_next(iter)) {
e = list_entry(iter, struct Edge, link);
length = base + e->weight;
if (length < distance[e->to]) {
HeapDecreaseKey(heap, size,
distance, reflection,
reflection[e->to], length);
parent[e->to] = root;
}
}
root = HeapRemoveTop(heap, size, distance, reflection);
base = distance[root];
if (distance[root] == INFINITY) {
/* remain nodes in heap is not accessible */
return g->V - (size + 1); /* 返回強連通分支結點數 */
}
} while (size);
/* successfull end algorightm */
return g->V;
}
╝④
再獻上一個實現
╔
C代碼
/*很裸很水的最短路，練習二叉堆優化的Dijstra～
之前二叉堆優化的Prim敲了好幾遍前後花了不下八個小時調試還是沒有調試成功，
但是還好，熟悉了優先隊列的操作。
十幾天後的今天重新想起這個，終於調出來了堆優化的Dijstra。理解之後還是蠻簡單的。
一些寫法並不是最優的，例如heap的實現中可以減少交換元素等。但是有這個自己寫的AC
過的Dijkstra在，以後寫二叉堆優化的Prim/Dijkstra和其它優先隊列的題目就可以拿它對照著Debug了。
2011-07-24 23:00
*/
#include <stdio.h>
#define MAXN 1200
#define MAXM 1200000
#define INF 19930317
struct node
{
int d, v, p;
}heap[MAXN];
int pos[MAXN], hl;
int e[MAXM], cost[MAXM], next[MAXM], g[MAXN], size;
int m, n, s, t;
void insert(int u, int v, int w)
{
e[++size] = v;
next[size] = g[u];
cost[size] = w;
g[u] = size;
}
void swap(int a, int b)
{
heap[0] = heap[a];
heap[a] = heap[b];
heap[b] = heap[0];
pos[heap[a].v] = a;
pos[heap[b].v] = b;
}
void heapfy()
{
int i = 2;
while (i <= hl)
{
if ((i < hl) && (heap[i + 1].d < heap[i].d))
i++;
if (heap[i].d < heap[i >> 1].d)
{
swap(i, i >> 1);
i <<= 1;
}
else
break;
}
}
void decrease(int i)
{
while ((i != 1) && (heap[i].d < heap[i >> 1].d))
{
swap(i, i >> 1);
i >>= 1;
}
}
void relax(int u ,int v, int w)
{
if (w + heap[pos[u]].d < heap[pos[v]].d)
{
heap[pos[v]].p = u;
heap[pos[v]].d = w + heap[pos[u]].d;
decrease(pos[v]);
}
}
void delete_min()
{
swap(1, hl);
hl--;
heapfy();
}
void init()
{
int u ,v ,w, i;
scanf("%d%d", &m, &n);
for (i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &w);
insert(u, v, w);
insert(v, u, w);
}
s = 1;
t = n;
}
int dijkstra()
{
int u, p, i;
for (i = 1; i <= n; i++)
{
heap[i].v = pos[i] = i;
heap[i].d = INF;
}
heap[s].p = s;
heap[s].d = 0;
swap(1, s);
hl = n;
while (hl)
{
u = heap[1].v;
delete_min();
p = g[u];
while (p)
{
if (pos[e[p]] <= hl)
relax(u, e[p], cost[p]);
p = next[p];
}
}
}
int main()
{
init();
dijkstra();
printf("%d\n", heap[pos[t]].d);
return 0;
}
╝③
╔
菲波那契堆實現
用類似的方法，使用Fibonacci Heap可以將復雜度降到O(E+VlogV)，但實現比較麻煩。因此這里暫不列舉。
❹ floyd演算法matlab
a矩陣是鄰接矩陣，對角線上為o，其餘位置數字表示的是兩點之間距離，比如a(1,2)=2,表示從第一個點到第二個點的距離為2.inf是無窮大的意思，這里表示沒有直接溝通這兩點的路。
n=length(d);設定n為d矩陣的長度。
接下來的兩重循環，得到的r矩陣是n*n的矩陣，它每個數據表示的是路徑，比如：r(1,3)=1;表示路徑為：1-1-3.這里是初始化路徑了。
後面的三重循環是floyd演算法的關鍵所在，就是更新路線了。裡面的那個判斷指的是：
假設有3個點，1
2
3；如果我從1-2-3之間總距離小於1-3的距離，那麼我r(1,3)=2；這就是選取更近的路線了。
最後的兩個判斷是為了不讓曾經走過的點再次被遍歷。就是不回頭的意思了，這個一般都可以忽略了，你照打上去就是了。
不知道這樣的解釋你是否滿意。
❺ 求matlab大神告訴我floyd演算法的matlab實現，，，以及我目前出現的各種報錯原因
存在負權的圖中沒有最短路的概念。負權迴路本來就沒有最短路。因為可以繞著負環一直轉下去。有兩個頂點:,->-->-然後我再由->那就成了-。
❻ 求程序 在matlab上用Dijkstra和Floyd演算法求出v1到v8的最短路徑。。
function[distance,path]=Dijkstra(W,st,e)
n=length(W);
D=W(st,:);
visit=ones(1:n);
visit(st)=0;
parent=zeros(1,n);
path=[];
fori=1:n-1
temp=[];
forj=1:n
ifvisit(j)
temp=[tempD(j)];
else
temp=[tempinf];
end
end
[~,index]=min(temp);
visit(index)=0;
fork=1:n
ifD(k)>D(index)+W(index,k)
D(k)=D(index)+W(index,k);
parent(k)=index;
end
end
end
distance=D(e);
t=e;
whilet~=st&&t>0
path=[t,path];
p=parent(t);t=p;
end
path=[st,path];%最短路徑
end
W=[0310InfInfInfInfInf;
30Inf5InfInfInfInf;
10Inf06InfInfInfInf;
Inf5604InfInfInf;
InfInfInf4095Inf;
InfInfInfInf9034;
InfInfInf105306;
InfInfInfInfInf460];
[distance,path]=Dijkstra(W,1,8);
>>distance
distance=
23
>>path
path=
124578
❼ 求matlab高手，幫我解決一下floyd演算法！！急急急
//假期在家做的，網上這類演算法很多，思想都差不多
#include<iostream>
using namespace std;
int N; //頂點個數
int max = 10000; //max代表兩點之間沒有路徑存在
float ** inPut(){
int edge,m,n,w,i;
cout<<"請輸入頂點數：";
cin>>N;
N = N+1; //矩陣（數組）下標從1開始計數，方便操作
float **C = new float*[N]; //矩陣C為圖的初始鄰接矩陣
for(i = 1; i<N; i++)
*(C+i) = new float[N];
for( i = 1; i<N; i++) //鄰接矩陣初始化
for(int j = 1; j<N; j++){
if(i == j)
C[i][j] = 0; //矩陣對角線上的值初始為0，其他為max
else C[i][j] = max;
}
cout<<"請輸入邊數：";
cin>>edge;
cout<<"請輸入邊及權值："<<endl;
for(i = 0; i<edge; i++){
cin >> m >> n >> w;
C[m][n] = w;
}
return C;
}
void Floyd(float **C){
int i,j;
float **A = new float*[N]; //矩陣A最終存放修改後的路徑長度
int **path = new int*[N]; //矩陣path記錄兩點之間的路徑
for(i = 1; i<N; i++)
*(A+i) = new float[N];
for(i = 1; i<N; i++)
*(path+i) = new int[N];
for(i = 1; i<N; i++) //設置矩陣A和path的初值
for(j = 1; j<N; j++){
if(C[i][j] != max)
path[i][j] = j; //存在路徑，記錄下終點下標值
else path[i][j] = -1; //不存在路徑用-1表示
A[i][j] = C[i][j];
}
//修改路徑長度（矩陣A）和路徑（矩陣path）
for(int k = 1; k<N; k++) //試圖將頂點k擴充到最短路徑path矩陣中
for(i = 1; i <N; i++)
for(j = 1; j<N; j++)
if( A[i][j] > ( A[i][k]+A[k][j] ) ){//判斷頂點i到j的權值是否大於從i經k到j的權值，取二者較小者記錄下來
A[i][j] = ( A[i][k]+A[k][j]);
path[i][j] = path[i][k]; //記錄下中間頂點k值
}
cout << endl << endl;
cout << "初始鄰接矩陣C[N][N]" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << C[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "修改後的路徑長度矩陣" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << A[i][j] << "\t";
}
cout << endl;
}
cout << endl;
cout << endl;
cout<<"路徑矩陣"<<endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << path[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "所有頂點對之間的最短路徑的權值及其路徑" << endl;
for(i = 1; i<N; i++){
cout << endl;
for(j = 1; j<N; j++){
cout << A[i][j] << "\t"; //輸出i-->j的權值
int next = path[i][j]; //頂點i到j的路徑，i後的第一個後繼頂點
if(next == -1) //路徑不存在
cout << i << " 到 " << j << " 沒有路徑" << endl;
else {
cout<<i; //起點
while(next != j){ //i、j之間存在中間頂點
cout << "-->" << next;
next = path[next][j]; //尋找下一個中間頂點
}
cout << "-->" << j << endl; //終點
}
}
}
}
int main(int argc, char* argv[]){
float **C;
C = inPut(); //鄰接矩陣的初始化
Floyd(C);
return 0;
}
/*
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
*/
❽ 想用Matlab中floyd演算法求最短路徑，可是不太會使用MATLAB2014怎麼辦怎麼導入Excel表進去
可以用下列命令，將Excel導入數組A中
A=xlsread('1.xls');
x=A(:,1); Excel第一列數值儲存到x列矩陣
y=A(:,2); Excel第二列數值儲存到x列矩陣
z=A(:,3); Excel第三列數值儲存到x列矩陣
。。。。。。
用xlswrite('2..xls', M)，將數組M寫入2..xls中
❾ floyd演算法求最短路徑
Floyd演算法適用於APSP(AllPairsShortestPaths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單
缺點：時間復雜度比較高，不適合計算大量數據。
時間復雜度:O(n^3)；空間復雜度:O(n^2)；
任意節點i到j的最短路徑兩種可能：
直接從i到j；
從i經過若干個節點k到j。
map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。
步驟：
第1步：初始化map矩陣。
矩陣中map[i][j]的距離為頂點i到頂點j的權值；
如果i和j不相鄰，則map[i][j]=∞。
如果i==j，則map[i][j]=0;
第2步：以頂點A(假設是第1個頂點)為中介點，若a[i][j] > a[i][1]+a[1][j]，則設置a[i][j]=a[i][1]+a[1][j]。
❿ 十萬火急需要用floyd演算法求最短路徑~~~需要程序~~~十萬火急~~~~~
A*演算法是啟發式搜索，適合點對點的最短路徑，單源單匯的情況
Floyd是動態規劃的一種，可以求出任意兩點之間的最短路徑
Dijkstra是貪婪演算法的一種，求一點到其他所有點的最短路，即所謂的單源最短路演算法
從時間復雜度來說
Floyd是O(N^3)
Dijkstra是O(N^2)
而啟發式搜索就不好說了……
結果當然是一樣的，都是最短路，但是適用情形和時空開銷就不同了
2011年