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 }\bm{dist[u]+w(u,v)<dist[v]}\text{ then update dist\lbrack v\rbrack}

4. Steps of the Algorithm

Initialize distances:
- dist[source] = 0
- all other dist[v] = ∞
Mark all vertices as unprocessed.
Insert source into a min-priority queue.
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.
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

powershell

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