C语言求图的最短路径的两种算法（迪杰斯特拉算法与弗洛伊德算法）

  本人小白一枚~最近在学数据结构，学到了如何求图的最短路径，以此贴来记录学习成果，如有写的不当的地方还请大佬指正。

参考资料：《大话数据结构》

1、迪杰斯特拉(Dijkstra)算法：

按路径长度递增依次求最短路径的算法。

从第一个顶点V0依次求到下一个顶点的最短路径，代码及注释如下

#include
#define maxsize 20
#define infinity 65535
typedef char VT;
typedef int ET;
typedef struct{
	VT vex[maxsize];
	ET arc[maxsize][maxsize];
	int numv,nume;
}MGraph;
int V0=0;
void ShortPath_Dijkstra(MGraph G,int V0,int *sn,int *sw);
void CreatMGraph(MGraph *G);
 
int main(void)
{
	MGraph G;
	int i;
	CreatMGraph(&G);
	int sn[G.numv];//前驱顶点下标 
	int sw[G.numv];//最短路径和 
	ShortPath_Dijkstra(G,V0,sn,sw);
	for(i=0;i",sn[i]);
	}
	printf("V%dn",G.numv-1);
	for(i=0;inumv,&G->nume);
	//for(i=0;inumv;i++){
	//	printf("请输入顶点V%d的值：n",i);
	//	scanf("%s",&G->vex[i]);
	//}
	for(i=0;inume;i++){
		for(j=0;jnume;j++){
			G->arc[i][j]=infinity;//初始化 
		}
	}
	for(k=0;knume;k++){
		printf("输入边(Vi,Vj)上的下标i与j和权w：n");
		scanf("%d %d %d",&i,&j,&w);
		G->arc[i][j]=w;
		G->arc[j][i]=G->arc[i][j];
	}
}

此算法嵌套了两个循环，因此其时间复杂度为O{n^2}，但是每次只能求一个顶点到其余各顶点的最短路径与最短路径长度，如第一次输入V0=0，只求出了V0到V8的最短路径与最短路径长度，要求V1到V8的最短路径长度则要重新输入V0=1再次进行复杂度为O{n^2}的过程。

2、弗洛伊德(Floyd)算法

建立两个二维数组，一个存储最短路径的权值，一个存储最短路径的前驱

代码如下：

#include
#define maxsize 20
#define infinity 65535
typedef char VT;
typedef int ET;
typedef struct{
	VT vex[maxsize];
	ET arc[maxsize][maxsize];
	int numv,nume;
}MGraph;

void ShortestPath_Floyd(MGraph G,int pw[][G.numv],int pn[][G.numv]);
void PrintShortestPath(MGraph G,int pn[][G.numv],int pw[][G.numv]);
void CreatMGraph(MGraph *G);

int main(void)
{
	MGraph G;
	CreatMGraph(&G);
	int pn[G.numv][G.numv];//  pn[i][j]表示从Vi到Vj最短路径的Vi经过的的下一个顶点 
	int pw[G.numv][G.numv];//  pw[i][j]表示顶点Vi间与Vj最短路径的权值
	ShortestPath_Floyd(G,pn,pw);
	PrintShortestPath(G,pn,pw);
	return 0;
}

void ShortestPath_Floyd(MGraph G,int pn[][G.numv],int pw[][G.numv])  //二维数组传参时只能省略1维的大小，不能省略更高维 
{
	int v,w,k;
	for(v=0;vpw[v][k]+pw[k][w]){
					pw[v][w]=pw[v][k]+pw[k][w];//   权值改为更小的有转折的 
					pn[v][w]=pn[v][k];//   前驱改为k 
				}
			}
		}
	} 
}

void PrintShortestPath(MGraph G,int pn[][G.numv],int pw[][G.numv])
{
	int v,w,k;
	for(v=0;vV%d",k);
				k=pn[k][w];  //获取下一个路径起点坐标且不打印终点 
			}
			printf("->V%dn",w);  //打印终点 
		}
	    printf("n");
	}
}

void CreatMGraph(MGraph *G)
{
	int i,j,k,w;
	printf("输入顶点数和边数：n");
	scanf("%d %d",&G->numv,&G->nume);
	//for(i=0;inumv;i++){
	//	printf("请输入顶点V%d的值：n",i);
	//	scanf("%s",&G->vex[i]);
	//}
	for(i=0;inume;i++){
		for(j=0;jnume;j++){
			G->arc[i][j]=infinity;//初始化 
		}
	}
	for(k=0;knume;k++){
		printf("输入边(Vi,Vj)上的下标i与j和权w：n");
		scanf("%d %d %d",&i,&j,&w);
		G->arc[i][j]=w;
		G->arc[j][i]=G->arc[i][j];
	}
}

Floyd算法显然比Dijkstra算法简洁很多，但是因为其初始化为两重循环，权值修正为三重循环，因此其时间复杂度为O{n^3}，真令人遗憾，不过这一算法可以一下子求出来所有顶点到其他顶点的最短路径与最小权值，当遇到要求所有顶点到其他顶点的最短路径与最小权值的问题时，这一算法一定是不错的选择。