条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。综上所述，可以得到图1311所示的伪代码，1将与s邻接的所有顶点的p初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s到i的最短路径，即是由s到它自身那条路径再扩充一条边得到。当找到更短的路径时，pi值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新d的值。
1初始化diasi（1≤i≤
），
f对于邻接于s的所有顶点i，置pis对于其余的顶点置pi0；对于pi≠0的所有顶点建立L表。2若L为空，终止，否则转至3。3从L中删除d值最小的顶点。4对于与i邻接的所有还未到达的顶点j，更新dj值为mi
djdiaij；若dj发生了变化且j还未在L中，则置pj1，并将j加入L，转至2。图111最短路径算法的描述1数据结构的选择我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d值最小的顶点。如果L用最小堆（见93节）来维护，则这种选取可在对数时间内完成。由于3的执行次数为O
，所以所需时间为O
log
。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d值，所以在4中可能需要改变一些d值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为：O有向图中的边数O
2，因此执行减操作的总时间为O
2log
。若L用无序的链表来维护，则3与4花费的时间为O
2，3的每次执行需OLO
的时间，每次减操作需1的时间（需要减去dj的值，但链表不用改变）。利用无序链表将图111的伪代码细化为程序135，其中使用了Chai
见程序38和Chai
Iterator类（见程序318）。程序135最短路径程序templatevoidAdjace
cyWDigraphShortestPathsi
tsTdi
tp寻找从顶点s出发的最短路径在d中返回最短距离在p中返回前继顶点ifs1s
throwOutOfBou
dsChai
L路径可到达顶点的列表
fChai
IteratorI初始化dpLfori
ti1i
idiasiifdiNoEdgepi0elsepisLI
sert0i更新dpwhileLIsEmpty寻找具有最小d的顶点vi
tvII
itializeLi
twINextwhilewifdwdvvwwINext从L中删除通向顶点v的下一最短路径并更新di
tivLDeletevfori
tj1j
jifaijr