欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的最短路算法(Dijkstra和Floyd-Warshall)

程序员文章站 2024-03-17 18:58:28
...

一、单源最短路(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;
                }
            }
        }
    }
}

举个生动而形象的栗子:
图的最短路算法(Dijkstra和Floyd-Warshall)
那么问题来了,如果要求所有顶点之间的最短路径,咋整?当然可以用n遍Dikstra,也有另一个赫赫有名的算法——floyd-warshall

二、全局最短路径——Floyd-Warshall 算法

基本思想

要求两个点之间的最短路径,那么,可能经过一些图中其他的点,会使两点间路径最短,接下来就是要不断地尝试在两点间加入其他点,使得路径变短。最终要求的最短路径就是在两点中尝试了插入n个点之后得到的最短路径。
例如:有点0、1、2、3,要求点2、3间的最短路径,先求出2、3间可以经过点0的最短路径,再求出2、3间可以经过点0、1的最短路径,此时的最短路径即为最终要求的最短路径。
注意,Floyd算法求的是整体最短路径,故每次加入一个点,都需要调整全局所有点之间的最短路径,方便之后的迭代,关于详细的步骤,下文会阐述,这张图是一个详细的例子,可以先看看,看不懂没关系,可以看完后面我对迭代方程的详细解释后再来通过这张图练习一下,强化对算法的理解。
图的最短路算法(Dijkstra和Floyd-Warshall)
迭代方程如下:
D1D_{-1}[i][j] = C[i][j]
DkD_k[i][j] = min{Dk1D_{k-1}[i][j],Dk1D_{k-1}[i][k] + Dk1D_{k-1}[k][j]}
其中DkD_k表示两点间此时的最短路径长度,且经过的点的序号最大为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