An extension of labeling techniques for finding shortest path trees

Athanasios K. Ziliaskopoulos*, Fotios D. Mandanas, Hani S. Mahmassani

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

Label setting techniques are all based on Dijkstra's condition of always scanning the node with the minimum label, which guarantees that each node will be scanned exactly once; while this condition is sufficient it is not necessary. In this paper, we discuss less restrictive conditions that allow the scanning of a node that does not have the minimum label, yet still maintaining sufficiency in scanning each node exactly once; various potential shortest path schemes are discussed, based on these conditions. Two approaches, a label setting and a flexible hybrid one are designed and implemented. The performance of the algorithms is assessed both theoretically and computationally. For comparative analysis purposes, three additional shortest path algorithms - the commonly cited in the literature - are coded and tested. The results indicate that the approaches that rely on the less restrictive optimality conditions perform substantially better for a wide range of network topologies.

Original languageEnglish (US)
Pages (from-to)63-72
Number of pages10
JournalEuropean Journal of Operational Research
Volume198
Issue number1
DOIs
StatePublished - Oct 1 2009

Keywords

  • Routing
  • Shortest path
  • Transportation

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'An extension of labeling techniques for finding shortest path trees'. Together they form a unique fingerprint.

Cite this