Dijkstra's Algorithm

Dec 7, 2025
Updated 1 day ago
2 min read
Abhijeet Singh Rajput
Abhijeet Singh Rajput
@abhijeetsingh

Dijkstra's Algorithm: Shortest Path Finder Explained

Dijkstra's Algorithm is a fundamental concept in graph theory and algorithm analysis, used to find the minimum cost path from a source vertex to all other vertices in a weighted graph. It is one of the most widely studied algorithms in computer science due to its efficiency and real-world applicability in areas like GPS navigation and network routing.

For related topics, see Greedy Approach for Algorithm Design and Graph Theory Notes.

1. Definition of Dijkstra's Algorithm

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

  • dist[] (Distance Array) → 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:

    • if dist[u] + w(u,v) < dist[v] then update dist[v]

4. Steps of Dijkstra's 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 of Dijkstra's Algorithm

  • 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

plaintext
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

For an authoritative reference, see Dijkstra's Algorithm on GeeksforGeeks and CP-Algorithms: Dijkstra.