定义

用于解决有权图中的最短路径问题，可以计算一个顶点到其余各顶点的最短路径。不过只能计算权值为正的有权图。

思路

需要记录开始节点到其余各节点的距离，各节点的前面节点以，还需要标记最优路径中的节点。初始时开始节点到所有节点的距离为无穷大。
初始化开始节点到开始节点为0，然后找到开始节点的相邻节点，得到开始节点到它们的距离，并记录它们的前面节点为开始节点。
之后重复一下两个步骤直到到达目标节点：
每次在未标记节点中寻找距离出发点最小的节点，标记为最优路径中的节点。
寻找当前标记节点的相邻节点，计算从开始节点经过该节点到达相邻节点的距离，和原先距离比较，若小于原先距离则更新，并标记前面节点为当前节点。

https://zhuanlan.zhihu.com/p/114203860