算法目的
以较小的时间复杂度求解加权有向图中一个源点到其余各个点的最短路径。
适用条件
图中不存在负权边。（否则，原点到原点的距离为0却不是最近的，显然违背了逻辑）
算法原理
将加权有向图中的点分为S和U两个集合，在S集合中，存储当前已经判断出和原点最小路径的点和相应到原点的最小距离的值；在U集合中，存储当前还未判断出最小距离的其他点。
算法的运行过程中，刚开始S集合中只放源点，如下图中原点是D，它距离原点（本身）的距离是0，因此记作S = {D(0)}；对于U集合当中的点表达方式亦然，但注意，如果一个点不和原点直接相连，则距离为∞。之后，每一次遍历，都选取U集合中距离原点D最小的点（记为i）存入S中，在图中将i点“抹去”（与此点直接相连的点将直接余原点相连，但此点到原点的距离不能抹去），更新与i点直接相连的U中点与源点的距离。直到所有U集合当中的点都被放入到S集合中，程序结束。S集合中存储的将是原点D到各个点的最小距离。
例子如下（下图引用自：/vqIlQ）：
相关习题
PAT甲级1003：Emergency(25）考点拓展
1. 图为无向图：
邻接矩阵需要存储双向的路径。
2. 附加第二标尺
除了寻找某两点之间的最短路径之外，还需要找到在最短路径（第一标尺）前提下的最大点权和路径/消耗时间最短路径（第二标尺），可以使用在第一标尺已经找到的情况下，使用DFS搜索找到第二标尺的方法；下文给出的是我习惯使用的方法——直接在找最短路径的过程中，每次向S集合移入结点时，都判断受到影响的其他结点（与其相邻的结点）的点权和/路径的消耗时间是否需要更新。简单而言，如下图所示：
解释：
在原来Dijkstra算法的基础上，每当图中有一个点（记为i）从U集合移入S集合，都要遍历与其相接的每一个点：
(a) 若该点（记为j）已经被放入S集合：
判断若i为j前向结点时，路径长度是否等于最小路径长度（因为S集合中存储点都是已经找到了最小路径了，不可能还有比它更短的路径），若是，进而判断“点权和/消耗时间”是否“大于原点权和/小于原消耗时间”，若是，再更新点权/消耗时间和以及前向结点；若i为j前向结点时，路径长度不等于最小路径长度，则不进行任何操作；
(b) 若该点（记为j）仍然在U集合：
判断若i为j前向结点时，若路径长度小于最小路径长度，则更新j结点的前向结点、点权和/消耗时间；若路径长度等于最小路径长度，则进一步“判断点权和/消耗时间”，若i为j前向结点的点权和大于了之前j最短路径的点权和/消耗时间小于原消耗时间，则更新的j结点的前向结点、点权和/消耗时间。
3. 需要输出最短路径的数目
在原来Dijkstra算法的基础上，每当图中有一个点（记为i）从U集合移入S集合，都要遍历与其相接的每一个点：
(a) 若该点（记为j）已经被放入S集合：
判断若i为j前向结点时，路径长度是否等于最小路径长度（因为S集合中存储点都是已经找到了最小路径了，不可能还有比它更短的路径），若是，则最短路径数目增加；若i为j前向结点时，路径长度不等于最小路径长度，则不进行任何操作；
(b) 若该点（记为j）仍然在U集合：
判断若i为j前向结点时，若路径长度小于最小路径长度，则更新前向结点、最短路径数目（继承前向结点路径数目）；若路径长度等于最小路径长度，则最短路径数目加一。
