最短路径算法——迪杰斯特拉Dijkstra和弗洛伊德Floyd

本文应该算是参考了该博主（戳这里飞往大佬的原文）有关此方面问题总结的一个读书笔记了吧。
Dijkstra算法
基本思想：设G=(V,E)是一个带权有向图（无向可以转化为双向有向），把图中顶点集合V分成两组（S和U）。其中，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将该点加入到集合S中，直到所有顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中顶点为中间顶点的当前最短路径长度。

具体步骤：
（1）初始时，S只包含源点，即S={v}，v的距离dist[v]=0。U包含除v外的其他顶点，U中顶点u距离dis[u]为边上的权值(若v与u有边)或∞(若u与v没有边)。
（2）从U中选取一个距离v(dist[k])最小的顶点k，把k加入到S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间的，修改U中各顶点的距离；若从源点v到顶点u（u∈U）的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，即如果dist[k]+w[k,u]<dist[u]，那么把dist[u]更新成更短的距离dist[k]+w[k,u]。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中（循环n-1次）。
贴代码：

#include<stdio.h>
#define MAX 100
#define INF 1000000000
int map[MAX][MAX];
int dis[MAX];
bool mark[MAX];//记录被选中的结点 
int n;
void dijkstra(int s)//求s借点到各结点的最短距离 
{
	int k;
	for(int i=0;i<n;i++)//初始化所有的结点都没有被选中 
		mark[i]=false; 
	for(int i=0;i<n;i++)//将每个结点到s结点的距离放入dis数组
		dis[i]=map[s][i];
	mark[s]=true;//s结点被选中 
	dis[s]=0;//将s结点的距离被设为0 
	int min;//最短距离
	for(int i=1;i<n;i++)//一共n-1次
	{
		min=INF;
		for(int j=0;j<n;j++)
		{
			if(!mark[j]&&dis[j]<min)
			{
				min=dis[j];
				k=j;
			}
		}
		mark[k]=true;//k结点被选中
		for(int j=0;j<n;j++)
		{
			if(!mark[j]&&(dis[j]>dis[k]+map[k][j]))
				dis[j]=dis[k]+map[k][j];
		} 
	}	
}
int main()
{
	int m,start,end;
	int a,b,c;
	printf("请分别输入顶点和边的数目:"); 
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			map[i][j]=INF;
	for(int i=0;i<m;i++)
	{
		printf("请输入第%d个边的起始点、终点和距离:",i+1);
		scanf("%d %d %d",&a,&b,&c);
		if(c<map[a][b]||c<map[b][a])
		{
			map[a][b]=c;
			map[b][a]=c;
		}
	}
	printf("请输入源结点和目标结点:");
	scanf("%d %d",&start,&end);
	dijkstra(start);
	printf("结点%d到%d的最短路径长度为:%d\n",start,end,dis[end]);
}

最短路径算法——迪杰斯特拉Dijkstra和弗洛伊德Floyd
Floyd算法
Floyd算法是解决任意两点间的最短路径的算法，可以处理有向图或负权值的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd算法原理的动态规划。
设D_i,j,k为从i到j的只以(1…k)集合中结点为中间结点的最短路径的长度。
若最短路径经过点k，则D_i,j,k=D_i,k,k-1+D_k,k,k-1；
若最短路径不经过k，则D_i,j,k=D_i,j,k-1。
因此D_i,j,k=min(D_i,k,k-1+D_k,k,k-1,D_i,j,k-1)。
如果dis[i][k]或者dis[k][j]不存在，我们可以用∞来代替。
真正的Floyd算法是一种基于DP的最短路径算法。
设图中G的n个顶点的编号为1到n。令c[i,j,k]表示从i到j的最短路径长度，其中k表示该路径中最大的顶点，也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此，如果G中包含边<i, j>，则c[i, j, 0] =边<i, j> 的长度；若i= j ，则c[i,j,0]=0；如果G中不包含边<i, j>，则c (i, j, 0)= +∞。c[i, j, n] 则是从i 到j 的最短路径的长度。
对于任意的k>0，通过分析可以得到：中间顶点不超过k的i到j的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c[i, j, k-1]，否则长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j, k]可取两者中的最小值。
状态转移方程：c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c [k, j, k-1]}，k＞0。

#include<stdio.h>
#define MAX 100
#define INF 10000000
int map[MAX][MAX],n;
int dis[MAX][MAX][MAX];
void floyd()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j][0]=map[i][j];
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				dis[i][j][k]=dis[i][j][k-1];
				if(dis[i][j][k]>dis[i][k][k-1]+dis[k][j][k-1])
					dis[i][j][k]=dis[i][k][k-1]+dis[k][j][k-1];
			}
} 
int main()
{
	int m,start,end;
	int a,b,c;
	printf("请分别输入顶点和边的数目:"); 
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j)
				map[i][j]=0;
			else
				map[i][j]=INF;
	for(int i=0;i<m;i++)
	{
		printf("请输入第%d个边的起始点、终点和距离:",i+1);
		scanf("%d %d %d",&a,&b,&c);
		if(c<map[a][b]||c<map[b][a])
		{
			map[a][b]=c;
			map[b][a]=c;
		}
	}
	floyd(); 
	printf("请输入源结点和目标结点:");
	scanf("%d %d",&start,&end);
	printf("结点%d到%d的最短路径长度为:%d\n",start,end,dis[start][end][n]);
	printf("请输入源结点和目标结点:");
	scanf("%d %d",&start,&end);
	printf("结点%d到%d的最短路径长度为:%d\n",start,end,dis[start][end][n]);
}

最短路径算法——迪杰斯特拉Dijkstra和弗洛伊德Floyd
小结：Dijkstra算法主要解决所有边的权为非负的单源点最短路径，Floyd算法可以检测图中的负环并可以解决不包括负环的图中全源最短路径问题。
Dijkstra算法直接实现时间复杂度是O(n²),空间复杂度是O(n)(保存距离和路径)，Floyd算法时间复杂度是O(n³)，空间复杂度是O(n²)；

最短路径算法——迪杰斯特拉Dijkstra和弗洛伊德Floyd

相关推荐