Dijkstra 算法 我们想找到A 与E(下图)之间的最佳路由。可以看到A 与E 之间有六条可能路径(ABE、ACE、ABDE、ACDE、ABDCE、ACDBE),很明显 ABDE 是最佳路由,因为它的权值最小。但是实际情况并非总是如此简单,有很多复杂的情形需要使用算法来找到最佳路由。 1. 如下图所示,源节点(A)被选为 T 节点,所以它的标号是永久(我们将永久性节点以实圈标注,T 节点以-->符号标注)。 2. 在这一步中,直接链接到T 节点的暂时性节点(B, C)的状态记录集已经被修改。同时,由于 B 有更小的权值,所以它被选作 T 节点,其标号被改为永久(如下图所示)。 3. 与步骤 2 类似,在这一步中,直接链接到T 节点的暂时性节点(D, E)的状态记录集已经被修改。同时,由于 D 有更小的权值,所以它被选作 T 节点,其标号被改为永久(如下图所示)。 4. 在这一步中,已经没有任何暂时性节点,所以我们仅仅需要确认下一个 T 节点。因为 E 有最小权值,所以它被选作 T 节点。 5. E 是目的节点,所以我们在这里停止。 我们已经到达了终点!现在,我们需要确定路由。E 的前序节点是D,D 的前序节点是B,B的前序节点是A。所以最佳路由是ABDE。在这个案例中,权值和为 4(1+2+1)。