图的最短路算法(Dijkstra和Floyd-Warshall)
一、单源最短路(Dijkstra算法)
基本思想
选定一个源点,按路径长度递增次序,逐步产生最短路径(贪心),直到此源点到其他各顶点的最短路径全部求出为止。
数据结构
带权有向图G=(V,E),V = 1,2,…,n,顶点1为源点。图的存储结构为带权矩阵C。
一维数组D[n]:D[i]表示从源点1到顶点i的当前最短路径长度,初始时,D[i] = C[1][i];
一维数组P[n]:P[i]表示源点1到顶点i的当前最短路径上,最后经过的顶点,初始时,P[i]=1(源点);
S[n]:存放源点和已生成的终点,其初态为只有一个源点1。
实现步骤
1、将V分成两个集合,S(到源点最短路径已经确定的点)和V-S。初始时,S中只有源点1
2、在V-S中选取一个顶点w,使D[w]最小,将w加入集合S中;
3、调整数组D、P,即取D[i]和D[i]+C[w][v]中的较小者;
4、重复2和3,直到S中包含V的所有顶点。
代码实现
typedef struct
{
int n, e;
int ver[MAX];
int EdgeWeight[MAX][MAX];
}DirectedWeightGraph/*图*/;
int MinWeight(int D[], bool S[])/*找到到源点路径最短的顶点*/
{
int temp = INT_MAX;
int w = 2;
for (int i = 2; i <= MAX; i++)
{
if (!S[i] && D[i] < temp)
{
temp = D[i];
w = i;
}
}
return w;
}
void Dijkstra(DirectedWeightGraph G, int D[MAX+1]/*表示从源点1到顶点i的最短路径长度*/, int P[MAX+1]/*表示源点1到顶点i的最短路径上最后经过的顶点*/, bool S[MAX+1])
{
int i, w, v, sum;
for (i = 1; i <= G.n; i++)/*初始化,各个顶点到源点最短为两点间距离*/
{
D[i] = G.EdgeWeight[1][i];
}
for (i = 1; i < G.n; i++)/*进行n-1次*/
{
w = MinWeight(D, S);/*找到当前到源点近的顶点*/
S[w] = true;/*将此顶点放入已经确定源点最短路径的顶点的集合*/
for (v = 2; v <= G.n; v++)/*更新现在剩下各点到源点的最短路径*/
{
if (S[v] != true)
{
sum = D[w] + G.EdgeWeight[w][v];/**即比较更新前此点到源点最短路径D[v]和更新后D[w]+C[w][v]的大小*/
if (sum < D[v])
{
D[v] = sum;
P[v] = w;
}
}
}
}
}
举个生动而形象的栗子:
那么问题来了,如果要求所有顶点之间的最短路径,咋整?当然可以用n遍Dikstra,也有另一个赫赫有名的算法——floyd-warshall
二、全局最短路径——Floyd-Warshall 算法
基本思想
要求两个点之间的最短路径,那么,可能经过一些图中其他的点,会使两点间路径最短,接下来就是要不断地尝试在两点间加入其他点,使得路径变短。最终要求的最短路径就是在两点中尝试了插入n个点之后得到的最短路径。
例如:有点0、1、2、3,要求点2、3间的最短路径,先求出2、3间可以经过点0的最短路径,再求出2、3间可以经过点0、1的最短路径,此时的最短路径即为最终要求的最短路径。
注意,Floyd算法求的是整体最短路径,故每次加入一个点,都需要调整全局所有点之间的最短路径,方便之后的迭代,关于详细的步骤,下文会阐述,这张图是一个详细的例子,可以先看看,看不懂没关系,可以看完后面我对迭代方程的详细解释后再来通过这张图练习一下,强化对算法的理解。
迭代方程如下:
[i][j] = C[i][j]
[i][j] = min{[i][j],[i][k] + [k][j]}
其中表示两点间此时的最短路径长度,且经过的点的序号最大为k。
由此迭代方程,我们可以先求出每两个点之间只会经过点0的最短路径,再迭代得到每两个点之间只经过0、1的最短路径……得到每两个点之间经过的点的序号不大于k的最短路径,若共有n个点,直到得到每两个点之间经过的点的序号不大于n-1的最短路径,即为结果。
数据结构
带权的n有向图采用邻接矩阵C[n][n]存储
数组D[n][n]:存放在迭代过程中求得的最短路径长度
数组P[n][n]:存放路径
实现步骤
1、初始化,A[i][j] = C[i][j];
2、k从0开始到n,对于每个k求出每两个点i、j之间的最短路径,调整方法就是利用上述的迭代方程;
代码实现
void Floyd(int D[][MAX], int C[][MAX], int P[][MAX]/**存放最短路径*/, int n)
{
int i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
D[i][j] = C[i][j];
P[i][j] = -1;
}
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (D[i][j] > D[i][k] + D[k][j])
{
D[i][j] = D[i][k] + D[k][j];
P[i][j] = k;
}
}
应用
很奇怪对不对,难道不是求出需要的两点间的最短路径就行了吗?为什么非要求出所有点之间的最短路径?
这个情况下就需要用到了:
一所未来会成为世界一流学校正在建,规划了几块地用来放教学楼啊、图书馆啊、宿舍啊、食堂啊等等。有的学生可能大学四年都不会去图书馆对不对,但是他总得去食堂吃饭啊,食堂肯定是每个人都要去的地方,那么食堂放在哪里呢?这时候选址的标准是什么?这时候就不需要哪一个建筑离食堂最近,而是需要离食堂最远的那个建筑不要离的太远。
可以让每个人都走15分钟到食堂,但不能让A同学下楼就到食堂了,B同学走一个小时才到食堂对不对。这时候求全局最短路径就派上用场了,对于每个点都知道了其他点到它的距离,比较一下每个点到其他点最远的距离即可。
若我哪里讲的不详细,有啥不懂的随时评论区讨论hhhh
推荐阅读
-
图的最短路算法(Dijkstra和Floyd-Warshall)
-
【经典算法实现 39】图的最短路径计算(优化Dijkstra算法支持负权计算 及 负环检测功能)(参考Bellman_Ford算法)
-
图论算法(二)-最短路径的Dijkstra [ 单源 ] 和Floyd[ 多源 ] 解法(JAVA )
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法
-
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
Java利用Dijkstra和Floyd分别求取图的最短路径
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法