An appraisal of some shortest-path algorithms. (English) Zbl 0172.44202

Dreyfus, S. E.

Oper. Res. 17, 395-412 (1969).

Summary: This paper treats five discrete shortest-path problems: (1) determining the shortest path between two specified nodes of a network; (2) determining the shortest paths between all pairs of nodes of a network; (3) determining the second, third, etc., shortest path; (4) determining the fastest path through a network with travel times depending on the departure time; and (5) finding the shortest path between specified endpoints that passes through specified intermediate nodes. Existing good algorithms are identified while some others are modified to yield efficient procedures. Also, certain misrepresentations and errors in the literature are demonstrated.

MSC:

90B10	Deterministic network models in operations research
90C35	Programming involving graphs or networks

Keywords:

shortest-path algorithms; networks