原理———之前看的一篇博客中有句解释这个过程的话感觉很棒：因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短， 如图： 按照算法的思路途中4个结点的遍历顺序是：v0、v1、v3、v2。第一次遍历过后我们选择了距离起点12的点v1，容易想到，我们不可能通过其他中转点，使得v0到v1的距离更短，但是我们可能通过v1这个中转点使得v0到v2或v3的距离更短。

如何记录路径——在算法的实现过程中，可以想到，我们得到的是一棵最短路径树，根据树的特点，每个结点都只有一个父亲结点，所以我们就可以用一个一维数组存储路径，最后从终点开始逐步向上层遍历到根节点（即起点），从而得到路径。如上图，第一次遍历过后v1、v2、v3的父亲结点都是v0；第二次遍历v1点时，发现v0通过v1到v2（v0–>v1–>v2）比v0直接到v2（v0–v2）更近，便更新v2的父亲结点为v1。 第一次遍历结束path数组：