Floyd算法直接使用二維數組求出所有頂點到所有頂點的最短路徑。
D代表頂點到頂點的最短路徑權值和的矩陣。
P代表對應頂點的最小路徑的前驅矩陣。
以下程序在DEV C++中調試運行通過。
#include <stdio.h> #define INFINITY 65535 typedef int VertexType; //頂點是字符型 typedef int EdgeType; //邊是整型 typedef struct //圖的鄰接矩陣存儲結構 { VertexType vexs[9]; //頂點向量 EdgeType edges[9][9]; //鄰接矩陣 int vexnum,arcnum; //圖中當前的頂點數和邊數 }MGraph; /* 鄰接矩陣的建立*/ void CreateGraph(MGraph *G) { int i,j,k,weight; int ch1,ch2; printf("請輸入頂點數和邊數(輸入格式為:頂點數,邊數):"); scanf("%d,%d",&(G->vexnum),&(G->arcnum)); printf("請輸入頂點名稱(輸入格式為:a,b,c...)："); for(i=0;i<G->vexnum;i++) { getchar(); scanf("%d",&(G->vexs[i])); } for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) if(i==j) G->edges[i][j]=0; else G->edges[i][j]=INFINITY; printf("請輸入每條邊對應的兩個頂點名稱(輸入格式為:a,b):/n"); for(k=0;k<G->arcnum;k++) { // getchar(); printf("請輸入第%d條邊的兩個頂點名稱：",k+1); scanf("%d,%d",&ch1,&ch2); for(i=0;ch1!=G->vexs[i];i++); for(j=0;ch2!=G->vexs[j];j++); getchar(); printf("請輸入第%d條邊的權值：",k+1); scanf("%d",&weight); G->edges[i][j]=weight; G->edges[j][i]=weight; } } void ShortestPath_Floyd(MGraph G,int P[9][9],int D[9][9]) { int v,w,k; for(v=0;v<G.vexnum;v++)//初始化D和P { for(w=0;w<G.vexnum;w++) { D[v][w]=G.edges[v][w]; P[v][w]=w; } } for(k=0;k<G.vexnum;k++) { for(v=0;v<G.vexnum;v++) { for(w=0;w<G.vexnum;w++) { if(D[v][w]>(D[v][k]+D[k][w])) {//如果經過下標為k頂點路徑比原兩點間路徑更短，將當前兩點間權值設為更小的一個 D[v][w]=D[v][k]+D[k][w]; P[v][w]=P[v][k]; } } } } } void main() { MGraph G; CreateGraph(&G); int i,j; printf("edgesnum:%d/n",G.arcnum); printf("vexesnum:%d/n",G.vexnum); for(i=0;i<9;i++) { for(j=0;j<9;j++) printf("%d ",G.edges[i][j]); printf("/n"); } int v,w,k; int P[9][9]; int D[9][9]; printf("%d/n",P); printf("%d/n",D); ShortestPath_Floyd(G,P,D); for(v=0;v<G.vexnum;v++)//顯示路徑 { for(w=v+1;w<G.vexnum;w++) { printf("v%d-v%d weight:%d ",v,w,D[v][w]); k=P[v][w]; printf("path:%d",v); while(k!=w) { printf("->%d",k); k=P[k][w]; } printf("->%d/n",w); } } } 運行結果如圖所示。
整個算法的時間復雜度是O(n^3)。
在編寫過程中遇到了以下錯誤：
在62行
[Error]subscripted value is neither array nor pointer nor vector
意思是
下標的值不是數組或指針或向量
當時我這一行是這樣寫的
void ShortestPath_Floyd(MGraph G,int** P,int** D)
因為在上一篇文章Dijkstra算法中一維數組作為函數參數是用的int*，沒有問題
所以在這里二維數組我就想當然地用了int**
但是如果參數傳入int**類型，在函數里就不能使用P[v][w]訪問二維數組的值
編譯器不能正確為它尋址，需要模仿編譯器的行為把P[v][w]這樣的式子手工轉變為：
*((int*)P + n*v + w);
所以在被調用函數中對形參數組定義時可以指定所有維數的大小，也可以省略第一維的大小說明
故改為void ShortestPath_Floyd(MGraph G,int P[9][9],int D[9][9])就可以編譯通過。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
