Figure 4

Propagation. Propagation procedure after the initialization, updates the start_path pointers. pred edges are represented as continued arrows, start_path pointers are represented as broken arrows.(a) If start_path[i] points to a node different from i (e.g. a predecessor of i) and different from start_path[start_path[i]] = j, then we assign start_path[i] = j. (b) If i has all the predecessors with start_path pointers pointing to themselves or predecessors with start_path pointing to the same node j, then we assign start_path[i] = j. (c) If all the predecessors of i have the start_path pointers cycling on themselves or start_path pointing to a node without predecessors, we consider the predecessor j having the maximum d _s distance and we assign start_path[i]= j.