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 |
| $\ell_e$ | For every edge $e\in E$ in a (directed) graph $G=(V,E)$, $\ell\ge 0$ is the length of the edge $e$. |
| $\ell(P)$ | Length of the path $P$, i.e. $\ell(P)=\sum_{e\in E} \ell_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_{u\in R, (u,w)\in E}\{d(u) + \ell_{(u,w)}\}$. |
| $P_u$ | The (unique) $s-u$ path in the "Dijkstra tree," which is also a shortest $s-u$ path in $G$ |