图论——最短路径——Floyd算法的证明[1.0]

小灰灰 2023-06-27 06:15 82阅读 0赞

#### Floyd算法简短介绍 ####

###### 思想： ######

Floyd算法考虑的是一条最短路径上的**中间结点**。  
什么是中间节点举个例子：  
一个简单路径p = <v1,v2,v3,…,vl>上的中间结点指的就是除了v1和vl之外的任意节点， 也就是处于集合<v2,v3,…,vl>内的结点。

Floyd算法是解决多源最短路径的一个算法， 它可以允许存在负边， 但不允许存在负环路。

#### 算法证明： ####

假设图G的所有节点V = \{1，2，…,n\}, 考虑其中的子结点k是某个小于n的整数。对于任意一对结点i, j ∈ V， 考虑从节点i到j的路径， 其所有中间结点均取自集合\{1,2,3…,k\}， 并且设当前的最短路径为p。  
Floyd算法利用的是已知p和 k = k-1时的关系(即\{1,2,3…,k-1\}时的关系)， 判断k是否是路径p上的一个中间结点。

*  如果k不是当前最短路径p上的中间结点， 则路径p上的中间结点都取自\{1, 2, …,k-1\}。因此他也中间结点都取自集合\{1，2，…,k\}的最短路径。
 *  如果结点k是路径p上的中间结点， 则可将路径p分解为 i – p1–> k —p2–> j。 如图1-1所示。根据引理24.1,p1是从结点i到结点k的最短路径， 并且其中间结点全部取自\{1，2，3,…,k-1\}。 同样, p2也是从节点k到结点j的最短路径， 中间结点全部取自\{1,2,3,…,k-1\}的一条最短路径。

基于上面的观察， 我们可以定义一个最短路径估计的递归公式。设dkij为从结点i到结点j的所有中间结点全部取自集合\{1，2，3，…,k\}的一条最短路径。当k = 0时， 从结点i到结点j的最短路径是一条不包含编号大于0的路径（即没有任何中间结点）。 这样的路径最多只有一条边, 因此， d0ij = wij。 根据上面的讨论， 递归定义dkij如下:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]  
图1-1\[来自算法导论\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70 1]  
(公式25.5)

所以当k = n时， 就计算出了最终答案。

###### 自底向上计算最短路径 ######

根据公式25.5，我们就可以使用自底向上的算法以递增次序计算dkij的值。  
这个算法的实现， 就是我们常说的三个for循环

这只是我个人的一个实现， 相信大家还求更好的实现方式
    for(k = 0;k < n;k++)
    	for(i = 0;i< n;i++)
    		for(j = 0;j <n;j++)
    			if(grap[i][k]!=inf&&grap[k][j]&&grap[i][j] > grap[i][k]+grap[k][j])
    				 grap[i][j] = grap[i][k]+grap[k][j];

#### 引理24.1: ####

这一引理简单的说就是：  
最短路径上的子路径也是最短路径。

具体内容如下：  
(最短路径的子路径也是最短路径)  
给定带权重的有向图G = (V,E)和权重函数wi, E→R,设p = <v0，v1，…, vk>为从结点v0到结点vk的一条最短路径， 并且对于任意的i和j ， 0<= i<=j <=k， 设pij = <vi,vi+1,…,vj>为路径p从结点i到结点j的子路径，那么pij是从结点i到结点j的一条最短路径。

#### 参考文献: ####

*  算法导论\[第三版\]

#### 附: ####

算法导论， 是从严谨证明的角度， 讲述算法一本书， 如果想要知道某些算法的更加严谨的证明过程， 算法导论是一本不错的书。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200104172057445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200104171859596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx,size_16,color_FFFFFF,t_70