relaxation
Checking whether going through vertex u gives a cheaper route to its neighbour v than the best one known, and updating v's distance if so.
In more detail
Relaxing edge (u, v) with weight w sets dist[v] = dist[u] + w when that is smaller. Dijkstra's algorithm relaxes each edge once, in a greedy order; Bellman-Ford relaxes every edge V minus one times, which lets it cope with negative weights.
Related terms
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- Bellman-Ford algorithm — A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.
- shortest path — The path between two vertices with the smallest total length: fewest edges in an unweighted graph, lowest total weight in a weighted one.
Taught in
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers