溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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 ch2,ch3;
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",&ch2,&ch3);
for(i=0;ch2!=G->vexs[i];i++);
for(j=0;ch3!=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])就可以編譯通過。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
