迪杰斯特拉算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值，其在运行过程中维持的关键信息是一组节点集合S。算法重复从结点集V-S中选择最短路径估计最小的结点u，将u加入到集合S，然后对所有从u发生的边进行松弛，运行结束后，从源节点到集合S中每个结点之间的最短路径已经被找到。 下面，通过一个实例讲解该过程！

如图，是一个有向无环图，假定出发点为V1，迪杰斯特拉算法将算出V1到其他所有点的最短路径，则所求V1到终点的最短路径也可得到，该算法主要完成以下几步：

完成后，将得到V1到所有点的最短距离，同时，通过每一个点记录的前驱得到最短路径。

松弛操作意味着比起原来的路径，找到了一条距离更短的路，则将原来点的距离更新为新的距离。注意本文中某个点的距离全部指的是从出发点即V1到该点的距离。代码如下：

我的理解是最短路是由最短路+某一条固定路组成，所以前驱适用全部点，比如该图中V1到V7的最短路径为V1->V2->V3->V5->V6->V7，因为V6->V7的距离固定为50，所以V7的最短路径中V1->V6的一段必然是V1->V6的最短路径，因此每个结点只需记录一个前驱。要想打印出路径，从终点开始一次次找前驱即可，可通过递归实现。代码如下：

程序运行过程中，数据的更新情况如图所示：

红色数据代表每次迭代中被更新的数据，下标代表了结点前驱。由上图可得，当所有结点加入S后，就得到了V1到所有结点的最短距离和最短路径，例如V1到V7的最短距离为130，V7的前驱为V6，V6的前驱为V5，V5的前驱为V3，V3的前驱为V2，V2的前驱为V1，则V1到V7的最短路径为V1->V2->V3->V5->V6->V7。