Leetcode每日一题(3)
有 N 个网络节点，标记为 1 到 N 。
给定一个列表 times ，表示信号经过 有向 边的传递时间。 times[i] = (u, v, w) ，其中 u 是源节点， v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例：
注意:
本题为一个图算法题，两点之间的时间可以抽象成路程，那么本题相当于求某一点到其他各点的最短路径，然后求出各点最短路径的最大值。
常见的最短路问题分为两类： 单源最短路 和 多源最短路 。前者只需要求一个 固定的起点 到各个顶点的最短路径，后者则要求得出 任意两个顶点 之间的最短路径。
Dijkstra(迪杰斯特拉)算法是典型的 单源最短路径算法 ，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法主要的思想是 贪心法 。
适用范围
使用步骤
Floyd算法是一个经典的 动态规划 算法。是解决 任意两点间的最短路径 (称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。
其核心思想就是从任意节点u到任意节点v的最短路径有2种：
所以，我们假设graph(u,v)为节点u到节点v的最短路径的距离(当然，不同的题目代表的不一样，比如有的可能是花费，需要灵活变通)，对于每一个节点k(1~N个节点)，我们检查graph(u,k) + graph(k,v) < graph(u,v)是否成立，如果成立，证明从u到k再到v的路径比u直接到v的路径短，我们便设置graph(u,v) = graph(u,k) + graph(k,v)，当我们遍历完所有节点k，graph(u,v)中记录的便是u到v的最短路径的距离。
适用范围
使用步骤
2.1、根据k为中间跳节点更新(u, v)的最短距离
Dijkstra算法
Floyd算法 (十分暴力)
堆优化版的Dijkstra算法
参考链接：
