Dijkstra's Algorithm: Weighted Shortest Path

Weighted Shortest Path

• Goal: Find the shortest path from start node s to all vertices v in a weighted graph G = (V, E, w).

Dijkstra's Algorithm

• Computes d(s, v) for all vertices v.
• Maintains a set S of settled vertices.
• For v in S, d(s, v) represents the true shortest distance.
• For v not in S, d(s, v) is the length of the shortest path to v using only settled vertices.

Dijkstra's Algorithm: Pseudo-code

• The algorithm initializes d(s, s) = 0 and d(s, v) = infinity for all v != s.
• While S (set of settled vertices) is not equal to V (all vertices):
  • Select vertex u not in S with the smallest d(s, u).
  • Add u to S.
  • For all neighbors v of u that are not in S:
    • Update d(s, v) as the minimum of the current d(s, v) and d(s, u) + w(u, v).

Dijkstra's Algorithm: Run Time

• Naive implementation: O(n^2 + m)
• Using a priority queue: O(m log n)
• n = |V|, m = |E|

Priority Queue

• Data structure supporting these operations:
  • Insert(key, value): Inserts a key-value pair.
  • ExtractMin(): Returns and removes the key-value pair with the smallest key.
  • DecreaseKey(key, new_value): Decreases the value of a key.

Priority Queue Implementations

• Binary heap: O(log n) for all operations
• Fibonacci heap: O(1) for Insert and DecreaseKey, O(log n) for ExtractMin (amortized)

Negative Edge Weights

• Dijkstra's algorithm fails with negative edge weights.

Bellman-Ford Algorithm

• Works with negative edge weights.
• Run Time: O(mn)