最短路路径（1.1版待更新）

一、只有5行代码的floyd算法：

1、 什么是floyd算法

弗洛伊德算法是解决多元最短路径的算法（什么是多源， 顾名思义就是起点有多个， 跑完floyd算法就算出以每个顶点做起点到各个点的最短路径）。

2、时间复杂度 O(n^3)

3、代码实现

for(k = 0;k < n;k++)
    for(i = 0;i< n;i++)
        for(j = 0;j <n;j++)
            if(grap[i][j] > grap[i][k]+grap[k][j])
                 grap[i][j] = grap[i][k]+grap[k][j];

4、原理

floyd算法用到的是动态规划的思想。
动规公式： grap[i][j] = min(gtap[i][j], grap[i][k]+grap[k][j]).
每次决策得到最优解。

该算法就是通过一个中间顶点k ，判断是否i通过k到达j的距离会更短（这一过程叫做松弛过程， 该算法通过多次的松弛得到最短路径）。

最短路路径（1.1版待更新）

原文：https://www.cnblogs.com/TJack/p/10586566.html