今天心血来潮看了几道最短路径题目，发现自己只记得弗洛伊德算法了，迪杰斯特拉算法忘得比太监的下巴还干净……明明之前还特意看过相关资料的……
例题：
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：输入：times = [[1,2,1]], n = 2, k = 2
输出：-1提示：
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、弗洛伊德算法
弗洛伊德算法实际上被视为一种动态规划，因为其有状态转移方程为：
maplen[i][j]=min(maplen[i][k]+maplen[k][j] , maplen[i][j])
这里 k 是 i 到 j 路径的另一种选择，当 y+z<x 时，最短路径就应该更改为 i->k->j。按照这样的理论，我们就可以通过比较找出最短路径。
为了方便我们记录并比较数据，一般会建立一个类似于离散数学中邻接矩阵的二维数组，其中存放各个点之间的路径长度。我们每次对于 i 到 j 之间的路径，将依次插入 1~n 个分支点（即试用所有的已知点来作为 ”k点“，排查最短路径），因此显然时间复杂度高达 O(n3) 。为了表示出两点间没有通路，一般把对应的数据填充为 ∞，代码使用 INT_MAX 来达到同样效果
初始化表格就是将现有的直接相连的路径记录在表格上，比如例题中示例一就应该是这样的：
随着后续路径更新，一些间接相连的数据也会记录上去，填充一部分 ∞。
这道题目中，为了判断是否出现了未完全链接的情况（即从源点无法和部分点形成通路），只需要检测源点对应那一行的状态即可，即全部不为无限长。不过因为只要检测这一行我们却老老实实的打了一整张表，未免有点太不划算了——因此我们请出了 迪杰斯特拉算法