Graph Algorithms • SSSP

Dijkstra's Algorithm

The Dijkstra algorithm finds the shortest path from a source vertex to all other vertices in a graph with non‑negative edge weights. It greedily selects the closest unvisited node at each step, guaranteeing optimal distances.

Try Interactive Simulator

Mechanism

Maintain tentative distances and visited nodes. Always pick the unvisited node with the smallest distance to explore next.

Priority Queue

A Min-Priority Queue efficiently provides the next node. Without it, finding the next node would take O(V) instead of O(log V).

Relaxation

When checking edge (u, v), if dist[u] + weight < dist[v], we update dist[v]. This is the core of path finding.

Constraints

Dijkstra fails with negative edge weights. For graphs with negative costs, use Bellman-Ford instead.

Dijkstra Algorithm

Dijkstra Algorithm

Dijkstra's Algorithm

Mechanism

Priority Queue

Relaxation

Constraints

Dijkstra's Algorithm

Mechanism

Priority Queue

Relaxation

Constraints