CSCI2100 · Definition · Chapter 14 · Graph algorithms
Relaxation
0 steps of prerequisites below it
For Dijkstra, dist[v] is the length of the shortest discovered source-to-v path; relaxing an edge (u, v) replaces dist[v] and the parent of v when dist[u] + w(u, v) is strictly smaller, and settling a vertex makes its label final.
Taught in
- 14.2 Weighted graph frontiers: Dijkstra and Prim · introduced
Builds on
Nothing in the notes sits below this point: it is a starting point.
Used by
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Nothing is recorded below this point: it is a starting point.