Dijkstra's Algorithm

Dijkstra’s Algorithm

1. Definition

Dijkstra’s Algorithm is a single-source shortest path algorithm used to find the minimum cost path from a source vertex to all other vertices in a weighted graph.

Conditions

• Graph must be connected.

• Edge weights must be non-negative.
  (Cannot be used for negative weights → use Bellman-Ford instead.)

2. Concept

It uses a Greedy Strategy:

Always pick the vertex with the minimum tentative distance that hasn’t been processed yet.

It gradually builds the shortest-path tree (SPT).

3. Key Terms

• Distance Array (dist[]) → stores shortest distance from source

• Visited Set → vertices whose shortest distance is finalized

• Priority Queue (Min-Heap) → efficiently picks smallest distance vertex

• Relaxation → updating distance of adjacent nodes

  $$\text{if }\mathbf{dist}[\mathbf{u}]+\mathbf{w}(\mathbf{u},\mathbf{v})<\mathbf{dist}[\mathbf{v}]\text{ then update dist[v]}$$

4. Steps of the Algorithm

1. Initialize distances:

   • dist[source] = 0

   • all other dist[v] = ∞

2. Mark all vertices as unprocessed.

3. Insert source into a min-priority queue.

4. While queue is not empty:

   • Extract vertex u with minimum distance.

   • Mark u as visited (its shortest path is finalized).

   • For each neighbor v of u:

     • Perform relaxation: update dist[v] if a shorter path is found.

5. Continue until all vertices are processed.

5. Output

• A Shortest Path Tree (SPT) from the source.

• Distance array showing minimum cost from source to every vertex.

6. Time Complexity

If adjacency matrix + linear search:

• O(V²)

If adjacency list + min-heap (optimal):

• O((V + E) log V)
  → Commonly written as O(E log V)

7. Space Complexity

• O(V) for distance array

• O(V) for visited array

• O(V) for priority queue

• Total → O(V)

8. Limitations

• Does NOT work with negative weight edges.

• Cannot detect negative cycles.

9. Applications

• GPS navigation systems (Google Maps, routing)

• Network routing protocols (OSPF)

• Robotics path planning

• Minimum time/cost problems

• Social network distance (closest connections)

10. Pseudocode

Dijkstra(Graph, source):
    for each vertex v:
        dist[v] = ∞
    dist[source] = 0

    create minPriorityQueue pq
    pq.push(source, 0)

    while pq is not empty:
        u = pq.pop()   // vertex with minimum dist

        for each neighbor v of u:
            if dist[u] + weight(u, v) < dist[v]:
                dist[v] = dist[u] + weight(u, v)
                pq.push(v, dist[v])

    return dist