数据结构之图的最短路径

╰半夏微凉° 2022-05-30 03:38 215阅读 0赞

**图的最短路径**

最短路径问题：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

下面讨论两种最常见的最短路径问题：**单源最短路径问题**和**所有顶点之间的最短路径**。

**1.单源最短路径问题：**给定一个带权有向图 D 与源点 v ，求从v 到 D 中其它顶点的最短路径。限定各边上的权值大于0。

如何求得这些路径？迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v 到其它各顶点的最短路径全部求出为止。

**解决步骤描述**：

1. 设置辅助数组dist。它的每一个分量dist\[i\]表示当前找到的从源点 v0到终点 vi的最短路径的长度；

2. 初始状态：

2.1. 若从源点 v0 到顶点 vi有边：dist\[i\]为该边上的权值；

2.2. 若从源点 v0 到顶点 vi无边：dist\[i\]为∞。

根据以上描述，可以得到如下描述的算法：

假设用带权的邻接矩阵Edge\[i\]\[j\]表示边(vi,vj)上的权值。若(vi,vj)不存在，则置Edge\[i\]\[j\]为∞。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。

1.初始化： ***S*** ← **\{ *v*0 \};dist\[j\]** ← **Edge\[0\]\[j\], j = 1, 2, …, *n*\-1;**  
2.找出最短路径所对应的点 ***K***：**dist\[*k*\] == min \{ dist\[*i*\] \}, *i*** ∈ ***V- S* ;*S*** ← ***S*** U **\{ *k* \};**  
3.对于每一个 ***i*** ∈ ***V- S*** 修改：**dist\[*i*\]** ← **min\{ dist\[*i*\],dist\[*k*\] + Edge\[*k*\]\[*i*\] \}；**  
4.判断：若 ***S = V*,** 则算法结束，否则转2。

算法的精髓：S 集内的顶点是已经找到最短路径的顶点，V0 到 w 的最短路径只能通过 S 集内的顶点。

![70][]

D\[w\] 可能改变:（解释算法第3条）  
if( D\[u\] + edge\[u,w\] < D\[w\] )  
\{  
D\[w\] = D\[u\] +edge\[u,w\] ;

![70 1][]

算法实现代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    #define VNUM 5           // 顶点数
    #define MV 65536         // 最大数值
    
    int P[VNUM];             // 辅助数组
    int Dist[VNUM];          // 存放最短路径，权值
    int Mark[VNUM];		 // 标记数组
    // 邻接矩阵定义图  MV表示顶点间没有变，不邻接
    int Matrix[VNUM][VNUM] =
    {
        {0, 10, MV, 30, 100},
        {MV, 0, 50, MV, MV},
        {MV, MV, 0, MV, 10},
        {MV, MV, 20, 0, 60},
        {MV, MV, MV, MV, 0},
    };
    // 迪杰斯特拉算法
    void Dijkstra(int sv)   // O(n*n)
    {
        int i = 0;
        int j = 0;
        // 合法性判断
        if( (0 <= sv) && (sv < VNUM) )
        {
        	// 初始化辅助数组
            for(i=0; i<VNUM; i++)
            {
                Dist[i] = Matrix[sv][i];
                P[i] = sv;                  // 最短路径的顶点的上一个顶点
                Mark[i] = 0;
            }
            // 标记顶点sv，即初始化集合S
            Mark[sv] = 1;
            // 循环求得sv到某个顶点的最短路径
            for(i=0; i<VNUM; i++)
            {
                int min = MV;                // 当前离sv顶点最短路径
                int index = -1;              // 下个最短路径的顶点
                // 遍历其余未被标记的顶点，找到最短路径及最短路径的顶点
                for(j=0; j<VNUM; j++)
                {
                    if( !Mark[j] && (Dist[j] < min) )
                    {
                        min = Dist[j];
                        index = j;
                    }
                }
                // 标记找到的最短路径的顶点，放入集合S中
                if( index > -1 )
                {
                    Mark[index] = 1;
                }
                // 更新当前最短路径及顶点
                for(j=0; j<VNUM; j++)
                {
                	// 修改：dist[i] ← min{ dist[i], dist[k] + Edge[k][i],i ∈ V- S 
                    if( !Mark[j] && (min + Matrix[index][j] < Dist[j]) )
                    {
                        Dist[j] = min + Matrix[index][j];
                        P[j] = index;
                    }
                }
            }
            // 打印最短路径及顶点
            for(i=0; i<VNUM; i++)
            {
                int p = i;
                // 顶点sv到其它顶点的路径
                printf("%d -> %d: %d\n", sv, p, Dist[p]);
                // 最短路径顶点关系
                do
                {
                    printf("%d <- ", p);
                    p = P[p];
                } while( p != sv );
                
                printf("%d\n", p);
            }
        }
    }
    // 测试函数
    int main(int argc, char *argv[]) 
    {
        Dijkstra(0);
        return 0;
    }

输出结果如下：

![70 2][]

分析算法可知，迪杰斯特拉算法的时间复杂度为O(n\*n)。

**2.所有顶点之间的最短路径**：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi≠vj，要求求出vi与vj之间的最短路径和最短路径长度。

解决这个问题的一个方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。虽然能实现，但是明显实现起来比较复杂。

下面介绍一下由弗洛伊德提出的另一个算法。这个算法的时间复杂度也是O(n3),但形势上简单些。

弗洛伊德算法仍从图的带权邻接矩阵Edge\[i\]\[j\]出发，其基本思想是：假设求顶点vi到vj的最短路径。如果从vi到vj有弧（无向图称为边），则从vi到vj存在一条长度为Edge\[i\]\[j\]的路径，该路径不一定是最短路径，尚需n次试探。首先考虑路径（vi ，v0 ，vj）是否存在（即判别弧(vi ，v0 )和弧(v0 ，vj)是否存在）。如果存在,则比较(vi ，vj)和(vi ，v0 ，vj)的路径长度取长度较短者为从vi到vj的中间定点序号不大于0的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果（vi ，…，v1）和（v1，…，vj）分别是当前找到的中间顶点的序号不大于0的最短路径,那么（vi ，…，v1，…，vj）就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推，若vi ，…，vk）和（vk，…，vj）分别是从vi到vk和从vk到vj中间顶点的序号不大于k-1的最短路径,则将（vi ，…，vk，…，vj）和已经找到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者是从vi到vj的中间顶点序号不大于k的最短路径。这样，经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

定义一个 n 阶方阵序列：***A*(-1), *A*(0), …, *A*(*n-*1)**  
其中:***A*(-1)\[*i*\]\[*j*\] = *Edge*\[*i*\]\[*j*\]  
*A*(*k*) \[*i*\]\[*j*\] = min \{ *A*(*k*\-1)\[*i*\]\[*j*\],*A*(*k*\-1)\[*i*\]\[*k*\] + *A*(*k*\-1)\[*k*\]\[*j*\]\}  
*k* = 0, 1, …, *n*\-1**

A(0)\[i\]\[j\]是从顶点vi到vj, 中间顶点是v0的最短路径的长度；  
A(k) \[i\]\[j\]是从顶点vi 到vj, 中间顶点的序号不大于k的最短路径的长度；  
A(n-1)\[i\]j\]是从顶点 vi 到 vj的最短路径长度。

举例：

初始状态

![70 3][]

第1次试探

![70 4][]

第2次试探

![70 5][]

第3次试探

![70 6][]

算法实现代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    #define VNUM 5           // 顶点数
    #define MV 65536         // 最大数值
    
    int P[VNUM][VNUM];       // 存放最短路径当前顶点
    int A[VNUM][VNUM];       // 存放最短路径
    // 邻接矩阵定义图  MV表示顶点间没有变，不邻接
    int Matrix[VNUM][VNUM] =
    {
        {0, 10, MV, 30, 100},
        {MV, 0, 50, MV, MV},
        {MV, MV, 0, MV, 10},
        {MV, MV, 20, 0, 60},
        {MV, MV, MV, MV, 0},
    };
    // 弗洛伊德算法
    void Floyd() // O(n*n*n)
    {
        int i = 0;
        int j = 0;
        int k = 0;
        // 2次嵌套循环，初始化路径和顶点
        for(i=0; i<VNUM; i++)
        {
            for(j=0; j<VNUM; j++)
            {
                A[i][j] = Matrix[i][j];          // 初始化路径
                P[i][j] = j;                     // 保存当前顶点
            }
        }
        // 3次嵌套循环，试探求最短路径
        for(i=0; i<VNUM; i++)
        {
            for(j=0; j<VNUM; j++)
            {
                for(k=0; k<VNUM; k++)
                {
                    if( (A[j][i] + A[i][k]) < A[j][k] )
                    {
                        A[j][k] = A[j][i] + A[i][k];     // 最短路径
                        P[j][k] = P[j][i];               // 标记当前顶点
                    }
                }
            }
        }
        // 显示最短路径
        for(i=0; i<VNUM; i++)
        {
            for(j=0; j<VNUM; j++)
            {
                int p = -1;
                // 顶点i到j的路径
                printf("%d -> %d: %d\n", i, j, A[i][j]);
                
                printf("%d", i);
                
                p = i;
                
                do
                {
                    p = P[p][j];           // 更新顶点
                    
                    printf(" -> %d", p);
                } while( p != j);
                
                printf("\n");
            }
        }
    }
    // 测试代码
    int main(int argc, char *argv[]) 
    {
        Floyd();
        
    	return 0;
    }

打印结果如下：

![70 7][]![70 8][]

Dijkstra最短路径算法是基于递推的思想设计的未达顶点的最短路径一定是由已达顶点的最短路径求出。

Floyd最短路径算法只是Dijkstra最短路径算法的加强，其本质还是递推。

[70]: /images/20220530/fb34e61ef4f54d62b0971dcc7a7e3e76.png
[70 1]: /images/20220530/1decd78282ec4e329d13a20338e0f41a.png
[70 2]: /images/20220530/ef032de8c29d40d5987ef5f575614182.png
[70 3]: /images/20220530/966338f5d4d14682a5437c1fd51f9091.png
[70 4]: /images/20220530/127777fb7a4f4b23ab22d4cf4724fdb7.png
[70 5]: /images/20220530/0191d98196cc41d9a7caff435ae61d62.png
[70 6]: /images/20220530/a96b2001b6db466ebd8ee5b2312c5e47.png
[70 7]: https://img-blog.csdn.net/20180304180357564?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDc1NDg0MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 8]: /images/20220530/a41c80476d274b5f81d0e8793660a6c9.png