A+DS

Dijkstra's Algorithm

Find the shortest path from one node to all others.

Dijkstra's algorithm finds the shortest path from a source node to every other node in a weighted graph. It greedily picks the closest unvisited node, then "relaxes" its neighbors — updating their distance if a shorter path is found through the current node.

     [A] --5-- [B] --2-- [D]
      |          |          |
      3          1          4
      |          |          |
     [C] --6-- [E] --3-- [F]

  Source = A
  dist[A]=0  dist[B]=5  dist[C]=3
  Relax B→D: dist[D] = 5+2 = 7
  Relax C→E: dist[E] = 3+6 = 9

How it works

  1. 1Set distance to source = 0, all others = ∞
  2. 2Pick the unvisited node with the smallest distance
  3. 3For each neighbor, check if going through current node is shorter
  4. 4If shorter, update the distance (relax the edge)

Loading...