最短路径：Dijkstra算法（求单源最短路径）Floyd算法（求各顶点之间最短路径）[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

最短路径：

在一个带权图中，顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径最短的那条路径称为最短路径。

DiskStra算法：

求单源最短路径，即求一个顶点到任意顶点的最短路径，其时间复杂度为O(V*V)

如图所示：求顶点0到各顶点之间的最短路径

代码实现：

#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50
#define MaxInt 32767
#define MaxEdgeNum 50
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
	VertexType vexs[MaxVexNum];//顶点表 
	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
	int vexnum,edgenum;//顶点数，边数 
}AMGraph; 

void createGraph(AMGraph &g){//创建无向图 
	printf("请输入顶点数：");
	scanf("%d",&g.vexnum);
	printf("\n请输入边数：");
	scanf("%d",&g.edgenum);
	
	//初始化顶点表 
	for(int i=0;i<g.vexnum;i++){
		g.vexs[i]=i; 
	} 
	for(int i=0;i<g.vexnum;i++){
		for(int j=0;j<g.vexnum;j++){
			g.arcs[i][j]=MaxInt;
			if(i==j) g.arcs[i][j]=0;
		}
	} 
	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
	for(int i=0;i<g.edgenum;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g.arcs[x][y]=w;
		//g.arcs[y][x]=w;
	}
}
void PrintGraph(AMGraph g){
	printf("邻接矩阵为:\n");
	for(int i=0;i<g.vexnum;i++) {
		printf("  %d",g.vexs[i]);
	}
	printf("\n");
	for(int i=0;i<g.vexnum;i++){
		printf("%d ",g.vexs[i]);
		for(int j=0;j<g.vexnum;j++){
			if(g.arcs[i][j]==32767){
				printf("∞ "); 
			}else{
				printf("%d  ",g.arcs[i][j]);
			}	
		}
		printf("\n");
	} 
}
//Dijkstra算法，求单源最短路径
void Dijkstra(AMGraph g,int dist[],int path[],int v0){
	int n=g.vexnum,v;
	int set[n];//set数组用于记录该顶点是否归并 
	//第一步：初始化 
	for(int i=0;i<n;i++){
		set[i]=0;
		dist[i]=g.arcs[v0][i];
		if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 
			path[i]=v0;//则更新路径i的前驱为v 
		}else{
			path[i]=-1; //表示这两点之间没有边
		 } 
	}
	set[v0]=1;//将初始顶点并入 
	path[v0]=-1;//初始顶点没有前驱
	
	//第二步 
	for(int i=1;i<n;i++){//共n-1个顶点 
		int min=MaxInt;
		//第二步：从i=1开始依次选一个距离顶点的最近顶点 
		for(int j=0;j<n;j++){
			if(set[j]==0&&dist[j]<min){
				v=j;
				min=dist[j];
		}
	}
	//将顶点并入 
	set[v]=1;	
	//第三步：在将新结点并入后，其初始顶点v0到各顶点的距离将会发生变化，所以需要更新dist[]数组
	for(int j=0;j<n;j++){
		if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){
			dist[j]=dist[v]+g.arcs[v][j];
			path[j]=v;
		}
	} 	
 } 
 //输出 
 printf("       ");
 for(int i=0;i<n;i++) printf("%d  ",i);
  
 printf("\ndist[]:");
 for(int i=0;i<n;i++) printf("%d  ",dist[i]);
 
 printf("\npath[]:");
 for(int i=0;i<n;i++) printf("%d  ",path[i]);

}

int main(){
	AMGraph g;
	createGraph(g);
	int dist[g.vexnum];
	int path[g.vexnum];
	Dijkstra(g,dist,path,0);
} 

Floyd算法：

求各顶点之间的最短路径,其时间复杂度为O(V*V*V)

如图所示，求<1,0>之间的最短路径：

代码实现：

#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50
#define MaxInt 32767
#define MaxEdgeNum 50
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
	VertexType vexs[MaxVexNum];//顶点表 
	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
	int vexnum,edgenum;//顶点数，边数 
}AMGraph; 

void createGraph(AMGraph &g){//创建无向图 
	printf("请输入顶点数：");
	scanf("%d",&g.vexnum);
	printf("\n请输入边数：");
	scanf("%d",&g.edgenum);
	
	//初始化顶点表 
	for(int i=0;i<g.vexnum;i++){
		g.vexs[i]=i; 
	} 
	for(int i=0;i<g.vexnum;i++){
		for(int j=0;j<g.vexnum;j++){
			g.arcs[i][j]=MaxInt;
			if(i==j) g.arcs[i][j]=0;
		}
	} 
	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
	for(int i=0;i<g.edgenum;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g.arcs[x][y]=w;
		//g.arcs[y][x]=w;
	}
}
void PrintGraph(AMGraph g){
	printf("邻接矩阵为:\n");
	for(int i=0;i<g.vexnum;i++) {
		printf("  %d",g.vexs[i]);
	}
	printf("\n");
	for(int i=0;i<g.vexnum;i++){
		printf("%d ",g.vexs[i]);
		for(int j=0;j<g.vexnum;j++){
			if(g.arcs[i][j]==32767){
				printf("∞ "); 
			}else{
				printf("%d  ",g.arcs[i][j]);
			}	
		}
		printf("\n");
	} 
}

//Floyd算法

//递归输出两个顶点直接最短路径 
void printPath(int u,int v,int path[][MaxVexNum]){
	if(path[u][v]==-1){
		printf("[%d %d] ",u,v);
	}else{
		int mid=path[u][v];
		printPath(u,mid,path);
		printPath(mid,v,path);
	}
}
void Floyd(AMGraph g,int path[][MaxVexNum]){
	int n=g.vexnum;
	int A[n][n];
	//第一步：初始化path[][]和A[][]数组 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			A[i][j]=g.arcs[i][j];
			path[i][j]=-1; 
		}
	}
	//第二步：三重循环，寻找最短路径 
	for(int v=0;v<n;v++){//第一层是代表中间结点 
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(A[i][j]>A[i][v]+A[v][j]){
					A[i][j]=A[i][v]+A[v][j];
					path[i][j]=v;
				}
			}
		} 
	} 
} 
 
int main(){
	AMGraph g;
	createGraph(g);
	PrintGraph(g);
	int path[MaxVexNum][MaxVexNum];
	Floyd(g,path);

	printPath(1,0,path);
} 

代码运行截图：