用C语言编程最短路径,C语言实现图的最短路径Floyd算法

C语言实现图的最短路径Floyd算法

发布时间&＃xff1a;2020-10-07 10:51:10

来源&＃xff1a;脚本之家

阅读&＃xff1a;64

作者&＃xff1a;KittyGirllll

Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。

D代表顶点到顶点的最短路径权值和的矩阵。

P代表对应顶点的最小路径的前驱矩阵。

以下程序在DEV C&＃43;&＃43;中调试运行通过。

#include

#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...)&＃xff1a;");

for(i&＃61;0;ivexnum;i&＃43;&＃43;)

{

getchar();

scanf("%d",&(G->vexs[i]));

}

for(i&＃61;0;ivexnum;i&＃43;&＃43;)

for(j&＃61;0;jvexnum;j&＃43;&＃43;)

if(i&＃61;&＃61;j)

G->edges[i][j]&＃61;0;

else

G->edges[i][j]&＃61;INFINITY;

printf("请输入每条边对应的两个顶点名称(输入格式为:a,b):\n");

for(k&＃61;0;karcnum;k&＃43;&＃43;)

{

// getchar();

printf("请输入第%d条边的两个顶点名称&＃xff1a;",k&＃43;1);

scanf("%d,%d",&ch2,&ch3);

for(i&＃61;0;ch2!&＃61;G->vexs[i];i&＃43;&＃43;);

for(j&＃61;0;ch3!&＃61;G->vexs[j];j&＃43;&＃43;);

getchar();

printf("请输入第%d条边的权值&＃xff1a;",k&＃43;1);

scanf("%d",&weight);

G->edges[i][j]&＃61;weight;

G->edges[j][i]&＃61;weight;

}

}

void ShortestPath_Floyd(MGraph G,int P[9][9],int D[9][9])

{

int v,w,k;

for(v&＃61;0;v

{

for(w&＃61;0;w

{

D[v][w]&＃61;G.edges[v][w];

P[v][w]&＃61;w;

}

}

for(k&＃61;0;k

{

for(v&＃61;0;v

{

for(w&＃61;0;w

{

if(D[v][w]>(D[v][k]&＃43;D[k][w]))

{//如果经过下标为k顶点路径比原两点间路径更短&＃xff0c;将当前两点间权值设为更小的一个

D[v][w]&＃61;D[v][k]&＃43;D[k][w];

P[v][w]&＃61;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&＃61;0;i<9;i&＃43;&＃43;)

{

for(j&＃61;0;j<9;j&＃43;&＃43;)

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&＃61;0;v

{

for(w&＃61;v&＃43;1;w

{

printf("v%d-v%d weight:%d ",v,w,D[v][w]);

k&＃61;P[v][w];

printf("path:%d",v);

while(k!&＃61;w)

{

printf("->%d",k);

k&＃61;P[k][w];

}

printf("->%d\n",w);

}

}

}

运行结果如图所示。

整个算法的时间复杂度是O(n^3)。

在编写过程中遇到了以下错误&＃xff1a;

在62行

[Error]subscripted value is neither array nor pointer nor vector

意思是

下标的值不是数组或指针或向量当时我这一行是这样写的

void ShortestPath_Floyd(MGraph G,int** P,int** D)

因为在上一篇文章Dijkstra算法中一维数组作为函数参数是用的int*&＃xff0c;没有问题

所以在这里二维数组我就想当然地用了int**

但是如果参数传入int**类型&＃xff0c;在函数里就不能使用P[v][w]访问二维数组的值

编译器不能正确为它寻址&＃xff0c;需要模仿编译器的行为把P[v][w]这样的式子手工转变为&＃xff1a;

*((int*)P &＃43; n*v &＃43; w);

所以在被调用函数中对形参数组定义时可以指定所有维数的大小&＃xff0c;也可以省略第一维的大小说明

故改为void ShortestPath_Floyd(MGraph G,int P[9][9],int D[9][9])就可以编译通过。

以上就是本文的全部内容&＃xff0c;希望对大家的学习有所帮助&＃xff0c;也希望大家多多支持亿速云。