迪杰斯特拉（Dijkstra）算法

对图中某一顶点来说，求它到图中其余各顶点的最短路径

以一个例子为例：

以结点A为源节点，计算结点A到其余各结点的最短路径（最小代价路径）

1、初始时，除了结点A外，其余结点全是临时结点，首先计算其余结点的符号标记：

对结点B来说，A到结点B的代价是2，所以 D(B)=2，而前序结点是A，所以 p(B)=A，因此结点B的符号标记是（2,A）；结点G同理

而其余结点都无法一步到达结点A，因此D=∞，p=没有。

2、在临时结点（图中蓝色结点中），选择D最小的结点加入永久结点（变成红色结点），更新该结点（所选到的D最小的结点）的所有邻居结点的符号标记

在临时结点中，B结点是D值最小的结点，因此将B结点加入永久结点，对B结点的邻居结点——E结点、C结点，更新标记值；以C结点为例，由于C结点原先的标记值是（∞，-），而 D(B)+c(B,C)=2+7=9，小于无穷，因此可以更新C结点的标记，更新成为(9,B)。

3、重复步骤2，直到所有结点都成为永久结点

当图中每一个结点都变成永久结点之后，图中每一个结点也就有了符号标记，沿着每个结点的符号标记中的 p （前序结点）画出一条路径，就是这个图，对于源节点 A的汇集树：

汇集树中，源结点A到任意结点的路径只有一条，且不会构成环