DAA Greedy Shortest Paths 28

Dijkstra’s Algorithm

Greedy rule: repeatedly extract the vertex with smallest tentative distance and relax its outgoing edges. Works when all edge weights are non-negative.

← Index ↗ Prim (27)

Graph (Plotly)

Speed
Preset Source s Target t Show weights
Settled (finalized)
0
Total relaxations
0
Extract-min
—
Priority Queue (conceptual)
—
Displayed as a sorted list by dist[v] (min-heap idea).
dist[] and parent[]
—
v dist[v] parent[v] settled?
Pseudocode (Dijkstra)
Line: —

Step Explanation

Click Start, then Step to extract-min and relax neighbors.

Notes & caveats
  • Dijkstra assumes no negative edge weights.
  • When a node is settled, its distance is final.
  • Typical runtime with heap: O((V+E) log V).

Course designed by Abhay Singh Bisht. Connect on LinkedIn →