The predecessor list is an array of indices, one for each vertex of a graph. Each vertex' entry contains the index of its predecessor in a path through the graph.

In this example, the red arrows show the predecessor relations, so the predecessor list would be: Vertex Predecessor pi s s* u x v x x s y x * Any convention to indicate a vertex with no predecessor will do: it can point to itself, as here, or be set to -1.

Key terms

Back to Dijkstra's algorithm

Back to the Table of Contents

© John Morris, 1998