带权有向图最短路径之Dijkstra和Floyd

---

一、单点最短路径之Dijkstra

迪杰斯特拉算法的思想是，将有向图中的顶点分为两个部分，一部分是已经确定了最短路径的节点，一部分是还未确定最短路径的节点。
每次从未确定的节点中挑选一个路径最短的出来放入到另一个集合中，直到所有的节点最短路径都确定。
 
算法步骤（每一轮）如下图：

如上图所示，每一轮都会确定一个节点，下一轮的时候，使用已经确定的节点来尝试缩短路径。
Dijkstra不支持带负权值的图。时间复杂度是$O(|V{|}^3)$。
 

二、所有节点之间最短路径之Floyd

Floyd算法属于动态规划算法，每次从图中挑选一个点作为中间节点，搜索以此中间节点为跳板是否可以减少其他两个节点之间的路径，然后更新最短路径。
 
算法步骤如下图所示：

Floyd允许图中有负权值，但是不允许回路中带负权值。
Floyd实现简单，时间复杂度为$O(|V{|}^3)$，空间复杂度为$O(|V{|}^2)$。