m数据结构 day15 图（五）最短路径算法(Dijkstra VS Floyd)

深藏阁楼爱情的钟 2023-03-13 09:25 6阅读 0赞

### 文章目录 ###

*  最短路径算法
 *   *  迪杰斯特拉算法 Dijkstra， O ( n 2 ) O(n^2) O(n2)，单源最短路径算法
     *   *  原理 （类似于最小生成树Prim算法）
         *   *  算法的依据
             *  算法的终极本质：贪婪，由近及远
             *  算法过程：更新-扫描-添加的迭代过程（不能更详细）
             *   *  示例
             *  其他相关结论
         *  代码，以邻接矩阵存储结构为例
         *  缺点
     *  弗洛依德算法 Floyd, O ( n 3 ) O(n^3) O(n3)，多源最短路径算法
     *   *  算法的本质：动态规划
         *  原理
         *   *  示例
         *  代码
         *   *  Floyd算法
             *  打印最短路径的代码

# 最短路径算法 #

最短路径的现实应用很多很多。

## 迪杰斯特拉算法 Dijkstra， O ( n 2 ) O(n^2) O(n2)，单源最短路径算法 ##

强调单源顶点查找路径的方式，符合人类的正常思路，所以原理容易被理解，但是代码比较复杂.

### 原理 （类似于最小生成树Prim算法） ###

#### 算法的依据 ####

如下图，从起点0到终点4的最短路径用黄色线标出，迪杰斯特拉算法思想诞生的依据是：如果这条路径是顶点0到顶点4的最短路径，那么**对于其中经过的每一个结点v，起点到v和v到终点的距离也都是最短的**。即起点到终点的最短路径由所有途径结点共享。所以我们就可以**先找到起点到其邻近结点的最短距离，然后一步步逐渐往终点延伸**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

#### 算法的终极本质：贪婪，由近及远 ####

迪杰斯特拉算法的终极本质：**先找到起点到其邻近结点的最短距离，然后一步步逐渐往终点延伸**。这也是贪婪算法的思想，所以迪杰斯特拉算法是一种贪婪算法，只不过他每一步找的当前最优（但是每一步找到的值后面的迭代过程中还可能变化，才能保证最终最优），一定可以保证最终也是最优。

#### 算法过程：更新-扫描-添加的迭代过程（不能更详细） ####

迪杰斯特拉算法很像得到最小生成树的prim算法，把顶点集合划分为已访问和未访问，或者说已选集合和未选集合。

和prim算法一样，用到三个辅助数组，但是含义略微不同：

*  visited: 每个顶点是否被访问，初始全为false。当一个顶点的visitesd被设置为true,则已经找到了起点到这个顶点的最短距离。
 *  distance: 从起点到每个顶点的最短距离，初始值全为inf
 *  每个顶点被访问时候的父亲顶点,初始值全为-1

迪杰斯特拉算法的执行过程：

*  假定起点为顶点0，设置visited\[0\]为true（把顶点0加入已选顶点集合）,并设置Distance\[0\]为0；
 *  更新update：每加入一个新顶点，就更新所有**位于未选顶点集合中，且与该新顶点相连**的顶点的**距离**信息。具体是：当新结点的距离加上边的权值小于distance中当前值，则更新distance值及parent数组，否则维持不变。
 *  扫描scan：扫描distance数组，找到未选顶点集合中distance值最小的顶点
 *  添加add:将其(未选顶点集合中distance值最小的顶点)加入已选顶点集合。visited数组对应位置设为true即可
 *  迭代第二三四步（更新-扫描-添加），直到所有顶点都被加入已选顶点集合，此时从起点0到任意顶点的最短距离及其路径都得到了。

##### 示例 #####

以下图的图为例，描述这个过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]

*  初始状态  
    ![在这里插入图片描述][20200514144609704.png]
 *  假定把顶点0作为起点（如果需要求顶点3到7的最短路和距离，则把3作为起点），则visited\[0\]设为true，distance\[0\]设为0。  
    ![在这里插入图片描述][20200514144635904.png]
 *  更新：新顶点是0，则更新位于未选顶点集合中，和新顶点相连（有边）的顶点的distance值。和0相连的是顶点1和7,0到1的距离4加上顶点0的距离0， 0 + 4 < i n f 0+4<inf 0\+4<inf，所以distance\[1\]更新为4，parent\[1\]为0； 0 + 8 < i n f 0+8<inf 0\+8<inf,所以distance\[7\]更新为8，parent\[7\]为0  
    ![在这里插入图片描述][20200514144759931.png]
 *  扫描：更新完毕，扫描当前distance数组中未选顶点的数值，找到最小值4，其顶点为1
 *  添加：把顶点1加入已选顶点集合，visited\[1\]为true。  
    ![在这里插入图片描述][20200514144841880.png]
 *  更新：新顶点是1，1连接到的未选顶点有2和7，到2的距离是顶点1自己的距离distance\[1\]加上边12的权值 d i s t a n c e \[ 1 \] + w 12 = 4 + 8 = 12 < i n f distance\[1\]+w12=4+8=12<inf distance\[1\]\+w12=4\+8=12<inf,所以更新distance\[2\]为12，parent\[2\]为1；到7的距离是 4 + 3 = 7 < 8 4+3=7<8 4\+3=7<8,8是上一次顶点0的迭代中设置的值，这次从顶点1到点7的距离才7，小于8，所以更新distance\[7\]=7,parent\[7\]=1  
    ![在这里插入图片描述][20200514145013805.png]
 *  扫描：未选顶点中distance最小的是顶点7
 *  添加：添加7
 *  对新顶点7做更新-扫描-添加迭代后：  
    ![在这里插入图片描述][2020051414551117.png]
 *  迭代新顶点8：8连到的未选顶点是2和6，到2的距离是 8 + 2 = 10 < 12 8+2=10<12 8\+2=10<12,更新；到6的距离是 8 + 6 = 14 > 13 8+6=14>13 8\+6=14>13,不更新；扫描到的最小距离顶点是2  
    ![在这里插入图片描述][20200514145830127.png]  
    迭代2:2连到的未选顶点是3和5，到3的距离是 10 + 7 < i n f 10+7<inf 10\+7<inf,更新；到5的距离是 10 + 4 < i n f 10+4<inf 10\+4<inf,更新;但是当前未选顶点的最小距离并不是3和5，而是之前的顶点6，添加6

![在这里插入图片描述][2020051415015539.png]

*  6连到的只有5，距离 13 + 2 > 14 13+2>14 13\+2>14，不更新；扫描到最小距离顶点是5吗，加入5  
    ![在这里插入图片描述][20200514150347989.png]
 *  5连到3和4，到3是 14 + 14 > 17 14+14>17 14\+14>17,不更新；到4是 14 + 10 < i n f 14+10<inf 14\+10<inf,更新；扫描后加入3  
    ![在这里插入图片描述][20200514150559353.png]
 *  3只连到4了，因为其他点都被选了。距离 17 + 9 > 24 17+9>24 17\+9>24,不更新。扫描时只有4一个点，加入4  
    ![在这里插入图片描述][2020051415082590.png]

#### 其他相关结论 ####

至此迪杰斯特拉算法结束，所有顶点加入了。我们来深入分析一下，可以发现：

1.  **顶点被加入到已选顶点集合的顺序一定是从近到远的**，以上面的示例为例，顶点被加入到已选顶点集合的顺序是：0(0)-1(4)-7(7)-2(10)-6(13)-5(14)-3(17)-4(24)，括号中是起点0到每个点的最短距离，可以看到确实是按照由近及远的顺序添加顶点的。
2.  每一个顶点只要被加入，**visited数组对应位置设为true，则当时distance数组对应位置一定存储的是起点到该顶点的最短距离**，不可能不是如此！！！比如下图中，0到1的距离是4，到7的距离是8，扫描发现1是最小距离顶点于是加入1，这时distance\[1\]=4一定是0-1的最短路径，因为从0出发到达1一开始只有两条岔路，0-7的那条岔路一条边都超过4了，肯定不可能再有比4短的路。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]
3.  最终**parent数组中存储了最短路径的顶点序列，而distance数组存储了起点到每一个顶点的最短路径的距离**。

可以通过parent数组画出最短路径（双线是路径，单线是parent数组中存储的其他走线，对我找0-4最短路径没用的线，线上数字是起点到线末尾顶点的最短距离）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]

### 代码，以邻接矩阵存储结构为例 ###

#define MAXVEX 100
    #define INF 65535
    void ShortestPath_Dijkstra(MGraph * G, int v0, int * distance, int * parent)
    { 
    	//参数v0是最短路径的起点，终点不用传入，因为迪杰斯特拉算法运行结束后可得到v0到任意顶点的最短路径
    	bool visited[MAXVEX];
    	int v;
    	//初始化三个数组
    	for (v=0;v<G->numV;++v)
    	{ 
    		visited[v] = false;
    		(*distance)[v] = G->arc[v0][v];//不初始化为INF，而是直接初始化为v0到各顶点的距离，更快一步
    		(*parent)[v] = -1;
    	}
    	//v0是起点
    	visited[v0] = true;
    	(*distance)[v0] = 0;
    	int min, w, k;
    	for (v=1;v<G->numV;++v)
    	{ 
    		min = INF;
    		//扫描所有未选顶点，找到最小距离顶点
    		for (w=0;w<G->numV;++w)
    		{ 
    			if (!visited[w] && (*distance)[w] < min)
    			{ 
    				min = (*distance)[w];
    				k = w;//最小距离顶点
    			}
    		}
    		//加入顶点k
    		visited[k] = true;
    		//为新加入的顶点k更新distance和parent数组,min是v0到顶点k的最短距离
    		for (w=0;w<G->numV;++w)
    		{ 
    			if (!visited[w] && min+G->arc[k][w]<(*distance)[w])
    			{ 
    				(*distance)[w] = min + G->arc[k][w];
    				(*parent)[w] = k;
    			}
    		}
    	}
    }

### 缺点 ###

迪杰斯特拉算法的缺点是：

*  从点v出发，一次性会找到v到其他所有顶点的最短路径，多做了很多不必要的事情，它的原理决定了它要找到某点v的最短路，就一定要找到图中所有其他顶点的最短路。因为找到达v的最短路依赖于其他所有顶点的协助，只有大家都最短了，才能确保到v的也是最短。所以时间复杂度没法再优化降低了。从时间复杂度上来说，迪杰斯特拉真的不算一个很好的办法，以顶点的数量的平方增长，但是找最短路本身也确实不容易。
 *  如果想知道图中**所有顶点到所有顶点的最短路径**，那就要对所有顶点执行一次迪杰斯特拉算法，总共时间复杂度就变成了 O ( n 3 ) O(n^3) O(n3)。（其实**弗洛伊德算法**求所有顶点到所有顶点的最短路径，**也是** O ( n 3 ) O(n^3) O(n3)。

## 弗洛依德算法 Floyd, O ( n 3 ) O(n^3) O(n3)，多源最短路径算法 ##

以算法精妙智慧，代码简洁优雅著称

完全抛开了单点的局限思维模式，巧妙的运用了矩阵的变换，用最清爽的代码实现了多顶点之间的最短路径的求解，原理理解难一点，但是代码很简洁。

### 算法的本质：动态规划 ###

### 原理 ###

需要用两个 n × n n\\times n n×n的辅助矩阵：

*  D: distance table,存储**图中任意两个顶点之间的最短路径的长度**。初始值为图的**邻接矩阵**。

比如这个图，这里是以有向图举例，但是无向图也可以用这本文这两个最短路径算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]  
其D矩阵的初始状态就是上图的邻接矩阵：  
![在这里插入图片描述][20200514170814850.png]

*  S：sequence table，存储**最短路径顶点序列**。初始化值为**终点**。  
    ![在这里插入图片描述][20200514170925140.png]  
    弗洛伊德算法要对图中的每一个顶点做一次迭代，以更新一次D和S矩阵，**所有顶点迭代完毕后的D,S矩阵就存储了最终的最短路径信息**。从S矩阵中找到v-w最短路径：
 *  v-w要经过S(v,w)，如果S(v,w)就是w，则v-w最短路径就是vw,即直达。如果S(v,w)不是w,则需要找S(v, S(v,w))和S(S(v,w),w)，依次找下去。

**对顶点u进行迭代的根本目的**是判断：**图中任意两个顶点v，w之间的最短路径是否可能经过结点u**。  
如果 d v u + d u w d\_\{vu\}+d\_\{uw\} dvu\+duw小于当前D(v,w), 则应该途径顶点u,更新S(v,w)为S(v,u),更新D(v,w)为 d v u + d u w d\_\{vu\}+d\_\{uw\} dvu\+duw；否则就不应该经过u。

这两个矩阵的更新是最为重要的，**注意D一定是更新为更短的距离，而S是更新为S(v,u)，即同一行的红色数字，即S从上一个S那里复制的固定不更新的标注为红色的数字。**

#### 示例 ####

对上述图做示例分析：

1.  初始化状态如上面两图所示，不再赘述。
2.  对顶点0迭代，称更新后的D和S为D0, S0（只有俩矩阵，重新命名是为了便于区分刚经过了顶点0的迭代过程）,首先把D和S的第0行第0列复制过来，然后填充D0和S0的所有空格位置。

填充的方法是什么呢？就是判断行数顶点到列数顶点的最短路径是否可能途径顶点0（现在在为顶点0做迭代），比如D0的第1行第2列，即1-2的最短路径是否可能途径顶点0， d 10 + d 02 = i n f + 8 d\_\{10\}+d\_\{02\}=inf+8 d10\+d02=inf\+8,而 d 12 d\_\{12\} d12本身也是inf,对于这种都是无穷大的，不用像数学上那样严格判断 i n f + 8 > i n f inf+8>inf inf\+8>inf,而是直接就算了，认为不经过顶点0了，因为最短路长度再大也不可能到达inf,没必要在inf尺度上计较盘算。于是D0(1,2)仍为inf，而S0(1,2)为2,表示从1直接到2，没经过别的点。

> **直接复制D的第0行第0列到D0**是因为：0-v(v=0,1,···，4)的最短路径一定要途径0，所以D0(0,v)都是确定值，就是0-v边的权值；而v-0的最短路径也必须经过点0，D0(v,0)也是v-0边的权值。就算不复制，走上面的计算流程，也会得到这组值，那不如直接复制，少了一部分判断。

为了便于观看和判断，我把复制过来的位置标红了,标红位置不需要更新。并且，对点u的迭代中，每一个空位D(i,j)的（ d i u + d u j d\_\{iu\}+d\_\{uj\} diu\+duj就是D(i,j)所在行的红色数字加上D(i,j)所在列的红色数字），很方便。

迭代前：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

看D0(1,3), d 10 + d 03 = i n f + i n f d\_\{10\}+d\_\{03\}=inf+inf d10\+d03=inf\+inf,太大了，不经过点0，D(1,3)现在存的直达距离 d 13 = 1 < < i n f d\_\{13\}=1<<inf d13=1<<inf，于是直接直达，所以D0(1,3)和S0(1,3)不更新

d 10 + d 04 d\_\{10\}+d\_\{04\} d10\+d04太大，不经过0，D(1,4)现在存的直达距离 d 14 = 7 d\_\{14\}=7 d14=7,所以D0(1,4)和S0(1,4)不更新

d 30 + d 01 = 2 + 3 = 5 < D ( 3 , 1 ) = i n f d\_\{30\}+d\_\{01\}=2+3=5<D(3,1)=inf d30\+d01=2\+3=5<D(3,1)=inf,所以这次应该经过点0，所以D0(3,1)=5,S0(3,1)=S(3,0)

d 30 + d 04 = 2 − 4 = − 2 < D ( 3 , 4 ) = i n f d\_\{30\}+d\_\{04\}=2-4=-2<D(3,4)=inf d30\+d04=2−4=−2<D(3,4)=inf,所以这次应该经过点0，所以D0(3,4)=-2,S0(3,4)=S(3,0)![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]

1.  对点1迭代，这次把D0,S0的第一行和第一列直接复制过来，迭代前（和D0，S0迭代后是一样的，我为了标红不需要更新的部分才单独再给一张图）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 7]

1.  对点2迭代，初始化状态：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 8]  
    D2(0,1)=3,红数字加和为12，大于原来的3，所以不走点2，D2(0,1),S2(0,1)都不更新，即0-1的最短路还是途径点1，直达。

D2(3,1)=5，大于红数字加和-1，所以应该走点2，即点3到点1的最短路径应该经过点2，而不是原来的点0，所以改D2(3,1)=-1,S2(3,1)=S(3,2)

结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 9]

1.  对点3和点4的迭代过程就不详述了，总之都是比较经过被迭代顶点的两路径之和是否小于当前D矩阵中的值，如果小于则应该经过被迭代顶点，并更新两个矩阵的值

直接给出对点3和点4迭代后的结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 11]

还有一个**很重要**的我写完代码才发现的点：**S矩阵在所有顶点迭代完毕后每一行的数字是一样的**，我之前以为是个巧合，没怎么管，但是我写文末的求v-w最短路径的代码时，发现，打印v-w的最短路径，发现的途径顶点k一定会被v直达从而可以直接打印在v后面，而迭代找到更多顶点一定是在k-w之间去找，即k更新为S(k,w)。比如，找0-1的最短路：

*  S(0,1)=4,所以途径4，路径变为0-4-1，我之前认为要分别看0-4和4-1之间是否还有顶点，但其实只需要看4-1，因为S(0,1)=S(0,4)=4,换言之，既然知道S(0,1)是4，那就知道了S矩阵第0行都是4，所以S(0,4)也是4，当然是直达。
 *  S(4,1)=3,所以4-1途径3，即0-4-3-1，4-3同理还是直达，因为S(4,3)一定也是3,所以只需要看3-1
 *  S(3,1)=2,所以3-1要经过2，路径变为0-4-3-2-1.
 *  S(2,1)=1,直达。最终路径：0-4-3-2-1

所以根据S矩阵找v-w的最短路径时，注意途径顶点k一定能够被它前一个顶点直达，而只需要查看k是否可以直达终点。**每一次都是在判断新找出的k是否可以直达终点w**。

从这个最终的S矩阵找2到0的最短路径：

*  S(2,0)为1，所以路径至少为2-1-0；
 *  找S(2,1)，为1，所以2-1是直达的；
 *  找S(1,0),为3，则路径至少为2-1-3-0，其中2-1是确定的
 *  找S(1,3),为3，所以1-3是直达的，中间没有别的点
 *  找S(3,0),为0，也是直达，所以3-0也是确定的，中间无点
 *  路线为2-1-3-0，权和为4+1+2=7，正是D(2,0)的值。

### 代码 ###

#### Floyd算法 ####

Floyd算法和迪杰斯特拉算法不一样的一点是：**后者是多源最短路径算法，前者是单源最短路径算法**。即：  
弗洛伊德算法可以从任意一点出发，拿到所有顶点到所有顶点的最短距离及其路径。但是迪杰斯特拉要找v到某点的最短路，则只能从v出发，并且找到的不仅是v到自己需要的终点的最短路，而是把v到任意其他顶点的最短路都找到了。

所以无须把起点作为参数传入下面的函数。

typedef int Pathmatrix[MAXVEX][MAXVEX];//Pathmatrix是int[MAXVEX][MAXVEX]类型
    typedef int ShortPathTable[MAXVEX][MAXVEX];
    /*Floyd算法，求网图G中顶点v到顶点w的最短路径及其距离*/
    void ShortestPath_Floyd(MGraph * G, Pathmatrix * S, ShortPathTable * D)
    { 
    	int v, w;
    	//初始化D和S矩阵
    	for (v=0;v<G->numV;++v)
        { 
    		for (w=0;w<G->numV;++w)
    		{ 
    			(*D)[v][w] = G->arc[v][w];
    			//if (v!=w)//对角线不管
    			(*S)[v][w] = w;
    		}
    	}
    	int k;
    	//主循环，三层嵌套
    	for (k=0;k<G->numV;++k)//从顶点0开始，迭代每一个顶点，以更新D和S
    	{ 
    		for (v=0;v<G->numV;++v)
    		{ 
    			for (w=0;w<G->numV;++w)
    			{ 
    				if (v!=w && v!=k && w!=k)//不更新对角线和第k行第k列的数据
    				{ 
    					if ((*D)[v][k]+(*D)[k][w] < (*D)[v][w])//如果途径k反而更短，则更新D和S，经过k
    					{ 
    						(*D)[v][w] = (*D)[v][k]+(*D)[k][w];
    						(*S)[v][w] = (*S)[v][k];
    					}
    				}
    			}
    		}
    	}
    }

哈哈，我对弗洛伊德真的理解了，关键代码自己写的。

时间复杂度分析:

*  初始化两层嵌套， O ( n 2 ) O(n^2) O(n2)
 *  主循环三层嵌套， O ( n 3 ) O(n^3) O(n3)

总的是 O ( n 3 ) O(n^3) O(n3)

#### 打印最短路径的代码 ####

/*打印所有顶点对之间的最短路径*/
    void printShortestPaths(MGraph * G, Pathmatrix * S, ShortPathTable * D)
    { 
    	int v, w;
    	//枚举法遍历所有顶点对
    	for (v=0;v<G->numV;++v)
    	{ 
    		for (w=v+1;w<G->numV;++w)
    		{ 
    			printShortestPath(S, D, v, w);
    		}
    		printf("\n");
    	}
    }
    
    /*打印顶点v到顶点w的最短路径*/
    void printShortestPath(Pathmatrix * S, ShortPathTable * D, int v, int w)
    { 
    	printf("v%d-v%d shortest distance: %d ", v, w, D[v][w]);
    	k = (*S)[v][w];
    	printf(" path: %d ", v);//打印路径的源点
    	while (k != w)//只需判断k是否可以直达终点，路径中k前面的点一定可以直达k,因为S矩阵每一行数字相同
    	{ 
    		printf(" -> %d ", k);
    		k = (*S)[k][w];
    	}
    	printf(" path: %d ", w);//打印路径的终点
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: /images/20230312/1cfb078fc3b542259decb6bb0ca23eb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: /images/20230312/b5fe7a7810144af980400e12b6efcc11.png
[20200514144609704.png]: /images/20230312/ea57612fc8ae4c20ab0642de5d32cf66.png
[20200514144635904.png]: /images/20230312/d9cb6a71008b46e7ab93b35762c7014a.png
[20200514144759931.png]: /images/20230312/feb4e69ef6ae4177b2e157677eaf3704.png
[20200514144841880.png]: /images/20230312/a4066ca47a5c40709c85e667a528a2a0.png
[20200514145013805.png]: /images/20230312/4ebc5c6c476a4401b57e1cd29a3842ba.png
[2020051414551117.png]: /images/20230312/da9a72e39b9548ef8617780aaa881b40.png
[20200514145830127.png]: /images/20230312/9369edd2ce66449795e4942a60f50983.png
[2020051415015539.png]: /images/20230312/f750910d15304c3597cae3df985b7022.png
[20200514150347989.png]: /images/20230312/b284801c0f2440039894b6ace8255c1b.png
[20200514150559353.png]: /images/20230312/d4e09823280547c69a1da275e80ae44b.png
[2020051415082590.png]: /images/20230312/78a90fbe54824e20a6214d94c870b567.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: /images/20230312/22dbe3aebe464e15920afaaef5e65134.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200514151601842.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200514170824223.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200514170814850.png]: https://img-blog.csdnimg.cn/20200514170814850.png
[20200514170925140.png]: https://img-blog.csdnimg.cn/20200514170925140.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200514195446772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200514195602154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200514195300525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200514193852122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200514195002438.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200514201635795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020051420492423.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200514205120580.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70