7. Shortest Paths
Robert Endre Tarjan · Society for Industrial and Applied Mathematics eBooks · 1983
7.1. Shortest-path trees and labeling and scanning. Another important network optimization problem is that of finding shortest paths. Let G be a directed graph whose edges have real-valued (possibly negative) lengths. We shall denote the length of an edge [v, w] by length (v, w). The length of a path p, denoted by length (p), is the sum of the lengths of the edges on p. A shortest path from a vertex s to a vertex t is a path from s to t whose length is minimum. The shortest-path problem is to find a shortest path from s to t for each member [s, t] of a given collection of vertex pairs. The paper of Dreyfus [7] is a good survey of early work on this problem. We shall consider four versions of the problem: