Dijkstra's algorithm

Dijkstra’s algorithm:

• Prerequisites:
  • All edges are weighted positively (as paths between vertices are assumed to be increasing, leading to a greedy step performed in the algorithm.
• Idea:
  • If a shortest path from A to C includes B, the path must contains the shortest path from A to B and one from B to C.
  • By using 2 mentioned fact, we can do DFS, selectively traverse along the vertices with the smallest path and are not visited, while updating adjacent vertices with the best paths, marking the least weighted edge as visited, until all vertices are visited.
  • During traversing and updating vertices, we can track the actual path with the vertex previously leading to it.
• Complexity: O((E + V).logV)
• Sudo code:

function Dijkstra(Graph, source):
      dist[source] ← 0
      create vertex priority queue Q
      for each vertex v in Graph.Vertices:
          if v ≠ source
              dist[v] ← INFINITY
              prev[v] ← UNDEFINED
         Q.add_with_priority(v, dist[v])
     while Q is not empty:
         u ← Q.extract_min()
         for each neighbor v of u:
             alt ← dist[u] + Graph.Edges(u, v)
             if alt < dist[v]:
                 dist[v] ← alt
                 prev[v] ← u
                 Q.decrease_priority(v, alt)
     return dist, prev