数据结构【图】—025最短路径距离

刺骨的言语ヽ痛彻心扉 2022-01-05 23:57 279阅读 0赞

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*迪杰斯卡特（Dijstra）\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

讲解：

1、Dijkstra算法介绍

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis\[s\] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis\[m\]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大(1e4)。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所

2、Dijkstra算法示例演示

下面我求下图，从顶点v1到其他各个顶点的最短路径

![1463063-20190323190043347-1477492404.png][]

首先第一步，我们先声明一个dis数组，该数组初始化的值为:

![1463063-20190323190052927-896290784.png][]

我们的顶点集T的初始化为：T=\{v1\}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis\[2\]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis\[2\]值。将V3加入到T中。

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis\[3\]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis\[3\]的值,得到如下结果：

![1463063-20190323190103427-230422184.png][]

因此 dis\[3\]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis\[3\]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis\[2\]和dis\[0\]外的其他值中寻找最小值，发现dis\[4\]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis\[4\]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis\[3\]的值为60，所以我们要更新dis\[3\]的值.另外，v1-v5-v6的长度为：90，而dis\[5\]为100，所以我们需要更新dis\[5\]的值。更新后的dis数组如下图：

![1463063-20190323190115528-1630538358.png][]

然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis\[3\]的值是最小的，所以把v4加入到集合T中，此时集合T=\{v1,v3,v5,v4\},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis\[5\]的值为90，所以我们要更新dis\[5\]的值，更新后的dis数组如下图：

![1463063-20190323190123261-123235139.png][]

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下：

![1463063-20190323190135073-1842231462.png][]

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

起点  终点    最短路径    长度

v1    v2     无          ∞

v3     \{v1,v3\}    10

v4     \{v1,v5,v4\}  50

v5     \{v1,v5\}    30

v6     \{v1，v5,v4,v6\} 60

算法实例：

先给出一个无向图

![1463063-20190323190143630-265222577.png][]

用Dijkstra算法找出以A为起点的单源最短路径步骤如下：

![1463063-20190323190150706-1156597228.png][]

具体实现的代码如下：

1 #define MAXEDGE 20
      2 #define MAXVEX 20
      3 #define INFINITY 65535
      4 
      5 struct MGraph{
      6     int vexs[MAXVEX];
      7     int arc[MAXVEX][MAXVEX];
      8     int numVertexes, numEdges;
      9 };
     10 
     11 //创建图的信息
     12 MGraph * CreateMGraph(MGraph *G)
     13 {
     14     int i, j;
     15 
     16     /* printf("请输入边数和顶点数:"); */
     17     G->numEdges = 16;
     18     G->numVertexes = 9;
     19 
     20     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
     21     {
     22         G->vexs[i] = i;
     23     }
     24 
     25     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
     26     {
     27         for (j = 0; j < G->numVertexes; j++)
     28         {
     29             if (i == j)
     30                 G->arc[i][j] = 0;
     31             else
     32                 G->arc[i][j] = G->arc[j][i] = INFINITY;
     33         }
     34     }
     35 
     36     G->arc[0][1] = 1;
     37     G->arc[0][2] = 5;
     38     G->arc[1][2] = 3;
     39     G->arc[1][3] = 7;
     40     G->arc[1][4] = 5;
     41 
     42     G->arc[2][4] = 1;
     43     G->arc[2][5] = 7;
     44     G->arc[3][4] = 2;
     45     G->arc[3][6] = 3;
     46     G->arc[4][5] = 3;
     47 
     48     G->arc[4][6] = 6;
     49     G->arc[4][7] = 9;
     50     G->arc[5][7] = 5;
     51     G->arc[6][7] = 2;
     52     G->arc[6][8] = 7;
     53 
     54     G->arc[7][8] = 4;
     55 
     56 
     57     for (i = 0; i < G->numVertexes; i++)
     58     {
     59         for (j = i; j < G->numVertexes; j++)
     60         {
     61             G->arc[j][i] = G->arc[i][j];
     62         }
     63     }
     64     return G;
     65 
     66 }
     67 
     68 void  ShortestPath_Dijkstra(MGraph *G) {
     69     vector<int>Res(MAXVEX, 0);//假设每个点的前向点都是v0点
     70     vector<int>Dis;//用来更新距离
     71     vector<bool>flag(MAXVEX, true);//记录已经遍历过的点
     72     int num = 0;//记录已经遍历过几个点了
     73 
     74     for (int i = 0; i < G->numVertexes; ++i) 
     75         Dis.push_back(G->arc[0][i]);//首先假设0到各个点的距离为最短路径，在此基础上进行更新
     76 
     77     int start = 0;//起始点
     78     flag[start] = false;//该点踢出下次的选择范围
     79     ++num;//记录遍历过的点
     80 
     81     while (num < G->numVertexes) {
     82         int min = INFINITY;//最小值
     83         for (int j = 1; j < G->numVertexes; ++j) {
     84             if (flag[j] && min > Dis[j]) {
        //从剩下的点中找到距离最小的值
     85                 min = Dis[j];
     86                 start = j;
     87             }
     88         }
     89 
     90         flag[start] = false;//该点踢出下次的选择范围
     91         ++num;//记录遍历过的点
     92 
     93         for (int i = 0; i < G->numVertexes; ++i) {
     94             if (flag[i] && G->arc[start][i] + Dis[start] < Dis[i]) {
        //经过start点再到达点i的距离是否比原来的短？
     95                 Dis[i] = G->arc[start][i] + Dis[start];//更短就更新为更短的距离
     96                 Res[i] = start;//更新前向点为start
     97             }
     98         }
     99     }
    100     
    101     stack<int>s;
    102     int end = G->numVertexes - 1;//记录
    103 
    104     while (end) {
        //使用压栈进行回溯出起始点到终点的路径
    105         s.push(end);
    106         end = Res[end];
    107     }
    108     s.push(end);
    109 
    110     while (!s.empty()) {
        //打印出路径
    111         cout << s.top() << "->";
    112         s.pop();
    113     }
    114     cout << endl << "总距离为：" << Dis[G->numVertexes - 1] << endl;
    115 }
    116 
    117 
    118 int T027(void) {
    119     int i, j, v0;
    120     MGraph *G;
    121     G = new MGraph;
    122     G = CreateMGraph(G);
    123 
    124     ShortestPath_Dijkstra(G);
    125     return 0;
    126 }

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*弗洛伊德（Floyd）算法\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

![1463063-20190323190439090-868061896.png][]

代码如下：

1 #include "000库函数.h"
      2 
      3 #define MAXEDGE 20
      4 #define MAXVEX 20
      5 #define INFINITY 65535
      6 
      7 struct MGraph {
      8     int vexs[MAXVEX];
      9     int arc[MAXVEX][MAXVEX];
     10     int numVertexes, numEdges;
     11 };
     12 
     13 //创建图的信息
     14 MGraph * CreateMGraph(MGraph *G)
     15 {
     16     int i, j;
     17 
     18     /* printf("请输入边数和顶点数:"); */
     19     G->numEdges = 16;
     20     G->numVertexes = 9;
     21 
     22     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
     23     {
     24         G->vexs[i] = i;
     25     }
     26 
     27     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
     28     {
     29         for (j = 0; j < G->numVertexes; j++)
     30         {
     31             if (i == j)
     32                 G->arc[i][j] = 0;
     33             else
     34                 G->arc[i][j] = G->arc[j][i] = INFINITY;
     35         }
     36     }
     37 
     38     G->arc[0][1] = 1;
     39     G->arc[0][2] = 5;
     40     G->arc[1][2] = 3;
     41     G->arc[1][3] = 7;
     42     G->arc[1][4] = 5;
     43 
     44     G->arc[2][4] = 1;
     45     G->arc[2][5] = 7;
     46     G->arc[3][4] = 2;
     47     G->arc[3][6] = 3;
     48     G->arc[4][5] = 3;
     49 
     50     G->arc[4][6] = 6;
     51     G->arc[4][7] = 9;
     52     G->arc[5][7] = 5;
     53     G->arc[6][7] = 2;
     54     G->arc[6][8] = 7;
     55 
     56     G->arc[7][8] = 4;
     57 
     58 
     59     for (i = 0; i < G->numVertexes; i++)
     60     {
     61         for (j = i; j < G->numVertexes; j++)
     62         {
     63             G->arc[j][i] = G->arc[i][j];
     64         }
     65     }
     66     return G;
     67 
     68 }
     69 
     70 void ShortestPath_Floyd(MGraph *G) {
     71     int Dis[MAXVEX][MAXVEX];//距离阵，进行更新
     72     int Path[MAXVEX][MAXVEX];//路径前向点的矩阵
     73 
     74     for (int i = 0; i < G->numVertexes; ++i) {
     75         for (int j = 0; j < G->numVertexes; ++j) {
     76             Dis[i][j] = G->arc[i][j];//将初始的临接矩阵赋值过来当初始距离阵
     77             Path[i][j] = j;//初始化路径的前向点
     78         }
     79     }
     80 
     81     for (int k = 0; k < G->numVertexes; ++k) {
     82         for (int i = 0; i < G->numVertexes; ++i) {
     83             for (int j = 0; j < G->numVertexes; ++j) {
     84                 if (Dis[i][k] + Dis[k][j] < Dis[i][j]) {
        //i经过k到j的距离会不会比直接到j的距离短？
     85                     Dis[i][j] = Dis[i][k] + Dis[k][j];//更新i到j的距离
     86                     Path[i][j] = Path[i][k];//i到j的路径中，要先从i到k
     87                 }
     88             }
     89         }
     90     }
     91     
     92     for (int i = 0; i < G->numVertexes; ++i) {
     93         int start = 0;//起始点固定为0
     94         vector<int>s;
     95         s.push_back(start);
     96         cout << "起点 0 到 " << i << " 的最短路径为： " << endl;
     97         while (s.size() < i) {
     98             start = Path[start][i];
     99             s.push_back(start);
    100         }
    101         for (auto a : s)
    102             cout << a << "—>";
    103         cout << "最短距离为：" << Dis[0][i] << endl;
    104     }
    105 }
    106 
    107 void T028() {
    108 
    109     MGraph *G;
    110     G = new MGraph;
    111     G = CreateMGraph(G);
    112     ShortestPath_Floyd(G);
    113 }

转载于:https://www.cnblogs.com/zzw1024/p/10585331.html

[1463063-20190323190043347-1477492404.png]: /images/20211228/2a62848e443f4bcd94a12649251440ea.png
[1463063-20190323190052927-896290784.png]: /images/20211228/073f0133ea9f4c6abdd7e655e4c776f1.png
[1463063-20190323190103427-230422184.png]: /images/20211228/cdbfbe52d0764e00a9ef50d03ce4d961.png
[1463063-20190323190115528-1630538358.png]: /images/20211228/0599c3dffbae4c728014c6780d51d3d0.png
[1463063-20190323190123261-123235139.png]: /images/20211228/ec2857688faf4a349a9989a7fe3be0b0.png
[1463063-20190323190135073-1842231462.png]: /images/20211228/48a97153cc1043288db76b9e86a33231.png
[1463063-20190323190143630-265222577.png]: /images/20211228/14f39e689181455f980baa1954d6ca8b.png
[1463063-20190323190150706-1156597228.png]: /images/20211228/3345b47bc997499c99a82e5b3c6ced07.png
[1463063-20190323190439090-868061896.png]: /images/20211228/d4b123d0a48b48f592f05da96d655bc2.png