A note on Bertsekas' small-label-first strategy
Zhilong Chen, Warren B. Powell · Networks · 1997
An example is presented to show that the worst-case complexity of Bertsekas' small-label-first strategy for the shortest path problem is exponential. It becomes polynomial if, when scanning a node i, its successors j ϵ Γ(i) are examined in the nondecreasing order of dij, the distance between i and j. © 1997 John Wiley & Sons, Inc. Networks, 29: 111–116, 1997