Notation for Shortest Path Problem
Here we collect notation related to shortest paths in graphs and algorithm to compute them.
Non-negative Graphs
Notation | Meaning |
ℓe | For every edge e∈E in a (directed) graph G=(V,E), ℓ≥0 is the length of the edge e. |
ℓ(P) | Length of the path P, i.e. ℓ(P)=∑e∈Eℓe. |
s | Source vertex s: we want to find shortest length path from s to every other vertex in G. |
d(t) | Length of the shortest s−t path. |
Dijkstra's Algorithm
Notation | Meaning |
R | Set of vertices "handled" by Dijkstra's algorithm at any point of time. Initialized to {s}. |
d′(u) | Best upper bound on d(u) that Dijkstra has at any point of time. Defined as d′(w)=min. |
P_u | The (unique) s-u path in the "Dijkstra tree," which is also a shortest s-u path in G |