floyd演算法代碼
1. 求Floyd演算法與選址C++原代碼
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define MAX_NAME 20
#define MAX_INFO 200
typedef int VRType;
typedef char VertexType[MAX_NAME];
#define INFINITY 65535
#define MAX_VERTEX_NUM 50
typedef struct
...{
VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
struct MGraph
...{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum;
int arcnum;
};
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//返回頂點在圖中的序號
int LocateVex(MGraph G,VertexType u)
...{
int i;
for(i =0; i< G.vexnum;i++)
...{
if(strcmp(u,G.vexs[i]) == 0)
return i;
}
return -1;
}
//read the file for creating the MGraph
int CreateDN(MGraph &G)
...{
FILE *fp;
char start_city_name[MAX_NAME];
char end_city_name[MAX_NAME];
int distance_of_city = 0;
fp=fopen("./ukcities.txt","r");
//init MGraph data
//頂點數量
G.vexnum = 0;
//初始化兩點之間的弧長信息,在這里即為兩個城市間的距離
//INFINITY在這里應當理解為無窮大的意思,65535隻是一個參考值
for(int p=0;p<MAX_VERTEX_NUM;++p)
for(int k=0;k<MAX_VERTEX_NUM;++k)
G.arcs[p][k].adj = INFINITY;
for(p=0;p<MAX_VERTEX_NUM;++p)
strcpy(G.vexs[p],"");
int m = 0;
for(int i=0;i<MAX_VERTEX_NUM;i++)
...{
fscanf(fp,"%s",start_city_name);
if(LocateVex(G,start_city_name) == -1)
...{
strcpy(G.vexs[m++],start_city_name);
G.vexnum++;
//printf("City Name: %s ", start_city_name);
}
fscanf(fp,"%s",end_city_name);
if(LocateVex(G,end_city_name) == -1)
...{
strcpy(G.vexs[m++],end_city_name);
G.vexnum++;
//printf("City Name: %s ", end_city_name);
}
fscanf(fp,"%d",&distance_of_city);
int iStart = LocateVex(G,start_city_name);
int iEnd = LocateVex(G,end_city_name);
//兩個城市間的距離
G.arcs[iStart][iEnd].adj = distance_of_city;
}
fclose(fp);
return 1;
}
//最短路徑的floyd演算法實現
void ShortestPathByFloyd(MGraph G,DistancMatrix &D)
...{
int u,v,w;
for(v=0;v<G.vexnum;v++)
...{
for(w=0;w<G.vexnum;w++)
...{
D[v][w] = G.arcs[v][w].adj;
}
}
for(u=0;u<G.vexnum;u++)
...{
for(v=0;v<G.vexnum;v++)
...{
for(w=0;w<G.vexnum;w++)
...{
if(D[v][u] + D[u][w] < D[v][w])
...{
D[v][w] = D[v][u] + D[u][w];
}
}
}
}
}
int GetTheShortestDistance(char start_city[],char end_city[])
...{
MGraph g;
CreateDN(g);
int i;
for(i=0;i<g.vexnum;i++)
...{
g.arcs[i][i].adj = 0;
}
DistancMatrix d;
ShortestPathByFloyd(g,d);
int nStart = LocateVex(g,start_city);
int nEnd = LocateVex(g,end_city);
if(nStart == -1)
...{
printf("This city is not exist:%s ",start_city);
return 0;
}
if(nEnd == -1)
...{
printf("This city is not exist:%s ",end_city);
return 0;
}
/**//*
int j;
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(d[i][j] == INFINITY)
{
printf("* ");
}
else
{
printf("%02d ",g.arcs[i][j]);
}
}
printf(" ");
}
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(d[i][j] == INFINITY)
{
printf("* ");
}
else
{
printf("%03d ",d[i][j]);
}
}
printf("@ ");
}
*/
if(d[nStart][nEnd] == INFINITY)
...{
return -1;
}
else
...{
return d[nStart][nEnd];
}
}
void main()
...{
int key;
char start_city[MAX_NAME];
char end_city[MAX_NAME];
do
...{
printf("Enter the start city name: ");
scanf("%s",start_city);
printf("Enter the end city name: ");
scanf("%s",end_city);
int nDistance = GetTheShortestDistance(start_city,end_city);
if(nDistance == -1)
...{
printf("Can't find the path from %s to %s ",start_city,end_city);
}
else
...{
printf("The shortest distance between %s and %s is %dkm ",start_city,end_city,nDistance);
}
printf("Press 'y' or 'Y' to continue or any key to quit! ");
}
while((key = getch()) == 'y' || key == 'Y');
}
源碼下載:
http://dl2.csdn.net/down4/20070705/05162441547.rar
2. matlab實現弗洛伊德演算法的代碼，。
function
[d,r]=floyd(a)
%floyd.m
%採用floyd演算法計算圖a中每對頂點最短路
%d是矩離矩陣
%r是路由矩陣
n=size(a,1);
d=a;
for
i=1:n
for
j=1:n
r(i,j)=j;
end
end
r
for
k=1:n
for
i=1:n
for
j=1:n
if
d(i,k)+d(k,j)
評論
0
0
0
載入更多
3. 用你熟悉的語言實現Floyd演算法，對於具有下面權重矩陣的有向圖求解完全最短路徑，截圖給出運行結果
Floyd的關鍵是三重循環和鬆弛式d[i][j] = min(d[i][j], d[i][k] + d[k][j])，代碼和注釋如下所示：
#include<bits/stdc++.h>
usingnamespacestd;
constintINF=1000000000;
constintn=5;
//鄰接矩陣
intd[][n]={
{0,2,INF,1,8},
{6,0,3,2,INF},
{INF,INF,0,4,INF},
{INF,INF,2,0,3},
{3,INF,INF,INF,0}
};
intmain()
{
//floyd
for(intk=0;k<n;++k)
for(inti=0;i<n;++i)
for(intj=0;j<n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//輸出結果
for(inti=0;i<n;++i){
for(intj=0;j<n;++j){
if(j>0)printf("");
if(d[i][j]==INF)printf("INF");
elseprintf("%3d",d[i][j]);
}
puts("");
}
return0;
}
運行結果圖：
4. floyd演算法導游問題
因為你只記錄了u是否是k到j的最短路徑上的點。。。並沒有記錄他們的相對順序啊
試一下這個代碼可以不
voidPrintShortestPath(constMGraph*G,int(&p)[10][10][10],intst,inted){
inti;
for(i=0;i<G->vexnum;i++){
if(i!=st&&i!=ed&&p[st][ed][i]){
PrintShortestPath(G,p,st,i);
PrintShortestPath(G,p,i,ed);
return;
}
}
printf("-->%s",G->vexs[ed].name);
}
voidFloyd(MGraph*G)
//用Floyd演算法求圖中各對頂點v和w之間的最短路徑P[v][w]及其
//帶權長度D[v][w]。若P[v][w][u]為1，則u是從v到w當前求得最短
//路徑上的頂點。
{
intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for(v=0;v<G->vexnum;v++)//各對結點之間初始已知路徑及距離
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w])//從v經u到w的一條路徑更短
{
D[v][w]=D[v][u]+D[u][w];//修改權值
for(i=0;i<G->vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while(flag)
{
printf("請輸入出發點和目的地的編號:");
scanf("%d%d",&k,&j);
if(k<0||k>G->vexnum||j<0||j>G->vexnum)
{
printf("景點編號不存在!請重新輸入出發點和目的地的編號:");
scanf("%d%d",&k,&j);
}
if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
flag=0;
}
printf("%s",G->vexs[k].name);
PrintShortestPath(G,p,k,j);
printf("總路線長%dm ",D[k][j]);
}//Floydend
5. 求解答以下Matlab Floyd演算法代碼的含義
暴力循環搜索。如果i，j之間存在k，使得i到j的距離大於i到k的距離加上k到j的距離，說明i-->k--j距離短，並把最短距離賦值給dij。很經典的最短路程序，只需要把距離矩陣套進去就行。
6. matlab floyd 演算法注釋
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;這就是選取更近的路線了。
最後的兩個判斷是為了不讓曾經走過的點再次被遍歷。就是不回頭的意思了，這個一般都可以忽略了，你照打上去就是了。
不知道這樣的解釋你是否滿意。
7. floyd演算法
核心思路
通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最後又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。
採用的是(鬆弛技術)，對在i和j之間的所有其他點進行一次鬆弛。所以時間復雜度為O(n^3);
其狀態轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}
map[i,j]表示i到j的最短距離
K是窮舉i,j的斷點
map[n,n]初值應該為0，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理,比如沒有map[i,k]這條路
編輯本段
演算法過程
把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。
定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。
把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。
在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3，D(3,1)=2，D(2,1)=1則說明從V5到V1經過V3，從V3到V1經過V2，V2到V1直接相連，路徑為{V5,V3,V2,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。
編輯本段
時間復雜度
O(n^3)
編輯本段
優缺點分析
Floyd演算法適用於APSP(All Pairs Shortest Paths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單；
缺點：時間復雜度比較高，不適合計算大量數據。
8. floyd演算法中輸出最短路徑序列的C語言代碼
void path(int i,int j)
{
int k;
if(P[i][j][i]==FALSE)
printf("There's no path!");
return;
for(k=0;k<n;k++)
if(P[i][j][k]==TRUE)
{
path(i,k);
path(k,j);
break;
}
}
void print(){
int v,w,u,i;
for (v=0;v<n;++v)
{
for (w=0;w<n;++w)
printf(" %d ",D[v][w]);
printf("\n");
}
printf("Please input the tailvex v1 and headvex v2:");
scanf("v1=%d,v2=%d",&v,&w);
path(v,w);
}
以上兩段應該對你有用。
9. floyd演算法杭電2544求指教，就一個點
for(int j=1;j<=n;j++)
{
f[i][j] = INF;
if(i==j)f[i][j] = 0;
}由這段代碼知道i!=j時，i到j的距離初始為無窮大INF的啊。如果C>INF在進行加的時候可能出現溢出吧。也就是說可能會有干擾數據。
10. floyd演算法的c程序代碼
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}