漫画：图的 “多源” 最短路径

╰半橙微兮° 2023-07-17 11:17 36阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

小灰的思路如下：

第一步，利用迪杰斯特拉算法的距离表，求出从顶点A出发，到其他各个顶点的最短距离：

![format_png 8][]

第二步，继续使用迪杰斯特拉算法，求出从顶点B出发，到其他各个顶点的最短距离。

第三步，从顶点C出发，到各个顶点的最短距离。

第四步，从顶点D出发......

.......

就像这样，一直遍历到顶点G。

这个思路的时间复杂度是多少呢？

假如图中有n个顶点，如果不考虑堆优化，一次迪杰斯特拉算法的时间复杂度是O（n^2）。所以，把每一个顶点都计算一遍，总的时间复杂度是O（n^3）。

![format_png 9][]

![format_png 10][]

![format_png 11][]

————————————

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

举一个栗子：

![format_png 20][]

上图的顶点A和顶点C没有直接相连的边，它们之间的直接距离是无穷大。

如果以B作为“中继顶点”，此时A到C的最短路径就是A-B-C，最短距离是3+2=5。

![format_png 21][]

再举一个栗子：

![format_png 22][]

上图的顶点A和顶点C直接相连，距离是6。但是存在一条“迂回”路径A-B-C，距离是3+2=5<6。

所以，经过中继顶点B，从A到C的最短距离可以是5。

![format_png 23][]

下面我们来看一看Floyd算法的详细步骤。

1.要实现Floyd算法，首先需要构建带权图的邻接矩阵：

![format_png 24][]

在邻接矩阵当中，每一个数字代表着从某个顶点到另一个顶点的直接距离，这个距离是没有涉及到任何中继顶点的。

2.此时假定只允许以顶点A作为中继顶点，那么各顶点之间的距离会变成什么样子呢？

B和C之间的距离原本是无穷大，此时以A为中继，距离缩短为AB距离+AC距离=

5+2=7。

更新对应矩阵元素（橙色区域代表顶点A到其他顶点的临时距离）：

![format_png 25][]

3.接下来以顶点A、B作为中继顶点，那么各顶点之间的距离会变成什么样子呢？

A和D之间的距离原本是无穷大，此时以B为中继，距离缩短为AB距离+BD距离=5+1=6。

A和E之间的距离原本是无穷大，此时以B为中继，距离缩短为AB距离+BE距离=5+6=11。

更新对应矩阵元素（橙色区域代表顶点B到其他顶点的临时距离）：

![format_png 26][]

4.接下来以顶点A、B、C作为中继顶点，那么各顶点之间的距离会变成什么样子呢？

A和F之间的距离原本是无穷大，此时以C为中继，距离缩短为AC距离+CF距离=2+8=10。

更新对应矩阵元素（橙色区域代表顶点C到其他顶点的临时距离）：

![format_png 27][]

.........

以此类推，我们不断引入新的中继顶点，不断刷新矩阵中的临时距离。

最终，当所有顶点都可以作为中继顶点时，我们的距离矩阵更新如下：

![format_png 28][]

此时，矩阵中每一个元素，都对应着某顶点到另一个顶点的最短距离。

![format_png 29][]

![format_png 30][]

为什么这么说呢？让我们回顾一下动态规划的两大要素：

**问题的初始状态**  
**问题的状态转移方程式**

对于寻找图的所有顶点之间距离的问题，初始状态就是顶点之间的直接距离，也就是邻接矩阵。

而问题的状态转移方程式又是什么呢？

假设新引入的中继顶点是n，那么：

**顶点i 到 顶点j 的新距离 = Min（顶点i 到 顶点j 的旧距离，顶点i 到 顶点n 的距离+顶点n 到 顶点j 的距离）**

![format_png 31][]

final static int INF = Integer.MAX_VALUE;
    
    
    
    public static void floyd(int[][] matrix){
    
    //循环更新矩阵的值
    
    for(int k=0; k<matrix.length; k++){
    
    for(int i=0; i<matrix.length; i++){
    
    for(int j=0; j<matrix.length; j++){
    
    if(matrix[i][k] == INF || matrix[k][j] == INF) {
    
    continue;
    
    }
    
    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
    
    }
    
    }
    
    }
    
    // 打印floyd最短路径的结果
    
    System.out.printf("最短路径矩阵: \n");
    
    for (int i = 0; i < matrix.length; i++) {
    
    for (int j = 0; j < matrix.length; j++)
    
    System.out.printf("%3d ", matrix[i][j]);
    
    System.out.printf("\n");
    
    }
    
    }
    
    
    
    
    
    
    
    
    
    public static void main(String[] args) {
    
    int[][] matrix = {
    
    {0, 5, 2, INF, INF, INF, INF},
    
    {5, 0, INF, 1, 6, INF, INF},
    
    {2, INF, 0, 6, INF, 8, INF},
    
    {INF, 1, 6, 0, 1, 2, INF},
    
    {INF, 6, INF, 1, 0, INF, 7},
    
    {INF, INF, 8, 2, INF, 0, 3},
    
    {INF, INF, INF, INF, 7, 3, 0}
    
    };
    
    floyd(matrix);
    
    }

![format_png 32][]

![format_png 33][]

[format_png]: /images/20230528/d880ceb051c4415e9daf5f203144a2ac.png
[format_png 1]: /images/20230528/f9103fac13c149eb839e26f716cea913.png
[format_png 2]: /images/20230528/34f189f9c06a45868f6fa85b39b214b9.png
[format_png 3]: /images/20230528/6678393e6c144159bc532700150152c5.png
[format_png 4]: /images/20230528/04142a5fb667483c9e1b4cf56ed64467.png
[format_png 5]: /images/20230528/74fac7f501b7469787530347fe7b3e25.png
[format_png 6]: /images/20230528/6266caae4b174d14ab0de46d6a4e9f44.png
[format_png 7]: /images/20230528/08e48e36aad54b41810f59c34ee9afac.png
[format_png 8]: /images/20230528/6f633677efb54fd691bcb84f13ffb386.png
[format_png 9]: /images/20230528/f9b90bc8a28b408894a4c5df48e7302e.png
[format_png 10]: /images/20230528/d08c8d2ddbc940f2bf829f0165248218.png
[format_png 11]: /images/20230528/add0cfb31bbc47768e915aac25a4d586.png
[format_png 12]: /images/20230528/467869fa850347b08a0a169c671dd505.png
[format_png 13]: /images/20230528/6fb4b3d5b9204640aac10ee4c567ee83.png
[format_png 14]: /images/20230528/f2def55794b246578ac73baf7efa5258.png
[format_png 15]: /images/20230528/c124fc96e1b24b94b59bc37611eba1cd.png
[format_png 16]: /images/20230528/294270686fa045108ba1fc9b86b00b85.png
[format_png 17]: /images/20230528/fae479b777e7406ab31f0c4903ec1d40.png
[format_png 18]: /images/20230528/9f4abaaddc4449aab334bb1e686743c3.png
[format_png 19]: /images/20230528/7433b0cc14374699b0e2b60c8a2b29c0.png
[format_png 20]: /images/20230528/f6e60147da1947ce87e2badd20b4ed06.png
[format_png 21]: /images/20230528/7f7e7434eb84458eb5515a3abb92b758.png
[format_png 22]: /images/20230528/cf5d1cdcf9d6490f9893a4bb99f05a84.png
[format_png 23]: /images/20230528/8828a9e368d048628ead8937f4ce6389.png
[format_png 24]: /images/20230528/72959f3559754e32994cddd55e11c5a4.png
[format_png 25]: /images/20230528/57282c77e9bc4fff841e7a930c3ce94d.png
[format_png 26]: /images/20230528/c2b32d8c7602409ab1033c5b91c3b94b.png
[format_png 27]: /images/20230528/51470fcaf6284b4db21dce0f0f9f31b9.png
[format_png 28]: /images/20230528/b60ccd172f66409c8e55950cc3b283ad.png
[format_png 29]: /images/20230528/4d4bc2dfbdae4e1e8a4cbb82e3df63da.png
[format_png 30]: /images/20230528/f89e3b2081a645dcab14c55c87f85ea9.png
[format_png 31]: /images/20230528/ed040d36f06e48b8a585ed84cfcd8977.png
[format_png 32]: /images/20230528/60144fb759a443b692570628dfe41a58.png
[format_png 33]: /images/20230528/04fffd6bc56244479ace534fdaee7908.png