Dijkstra's

Time Complexity

insert times

• Each node is added to priority queue once relax/decreaseKey times
• Each edge is relaxed once

Implementation of queue	insert	deleteMin	decreaseKey	Time complexity
Array
AVL Tree
d-way Heap				)$
Fibonacci Heap

Proof of Correctness

Proof by induction

1. Every finished vertex has correct estimate.
2. Basis step: The start vertex is finished and has a correct estimate.
3. Inductive step:
   1. Remove vertex from priority queue
   2. Relax edges
      • Changes priority if there is a vertex in priority queue with less priority
   3. Add vertex to set of finished vertices
   4. Estimate of vertex is final

Invariants

1. Vertex is finished when dequeued.
   • Estimate is never changed
   • When destination is reached, we can stop the algorithm

Limitations

1. Fails with negative weights.
2. Graphs cannot be reweighted.