A note on Bertsekas' small-label-first strategy

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)111-116
Number of pages6
Issue number2
StatePublished - Mar 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


  • Labeling algorithm
  • Shortest path problem
  • Worst-case complexity


Dive into the research topics of 'A note on Bertsekas' small-label-first strategy'. Together they form a unique fingerprint.

Cite this