Shortest paths in a weighted graph

Variations

Single-destination shortest paths problem - find a shortest path to a given destination from every vertex
Single-pair shortest path problem - find a shortest path from source to destination
All-pairs shortest paths problem - find a shortest path between any two vertices We will focus on a single-destination variation

Input

Output

Shortest path lemma from previous lecture (BFS, DFS) also applies here in a more general form:

Let us first define a function calculating the minimal distance in the following way:

This function only works for acyclic(!) graphs, and runs in Similar solution with the same complexity is to first perform the topological sort and then go in that order instead of a random one.

What can we do with cycles? Cycles can be classified:

Negatively weighted cycle, this would mean that we can achieve distance, problematic
Zero-weighted cycle, this cycle can just be ignored as it doesn’t affect the distance
Positively-weighted cycle, a “regular” cycle, can also be ignored

Let’s assume we have no negative cycles

Relaxation technique

Initialize all vertices to have a distance estimate

For each edge in , relaxing an edge means checking whether an edge can improve the current shortest path, and thus should be used

No-path property lemma

Upper-bound property lemma

Convergence property lemma

Path-relaxation property lemma

Bellman-Ford algorithm (excluding negative cycles)

Algorithm runs in

Dijkstra’s algorithm

Assume we have no negative weighted edges. Dijkstra’s algorithm maintains a set of vertices that have their shortest paths from already determined. The algorithm then repeatedly selects with the minimum distance estimate (relaxation technique), adds to and relaxes all edges from

Note that updates the key in , so it has to also call , which makes it for binary heap min queue instead of If using binary heap min queue, the runtime is If using Fibonacci heap min queue, the runtime is

Cub11k's BIU Notes

Explorer

Algorithms-1 04