Dijkstra’s Algorithm
Complete Guide & Visualizer

In many real-world systems – like maps, networks, and transportation – we need to move from one place to another using the lowest possible cost (distance, time, or any other weight). Dijkstra’s Algorithm is a classic solution to thesingle-source shortest path problem in a graph with non-negative edge weights.

Goal: Given a weighted graph and asource node, find the shortest path from the source to every other node.

Project / Assignment Purpose

• Understand the logic behind Dijkstra’s Algorithm.
• Implement and visualize shortest path computation.
• Study its complexity, limitations, and applications.
• Compare it with other search algorithms like A* and Greedy BFS.

This website acts as a combined report + visual toolfor your Dijkstra assignment or mini-project.

2.1 Graph Model

• Vertices (V): represent cities, routers, locations, etc.
• Edges (E): represent connections (roads, links, paths).
• Weights w(u, v): cost of going from node u to v.

Dijkstra’s algorithm assumes thatall edge weights are non-negative. If negative edges are present, the algorithm may produce incorrect results.

2.2 Key Ideas

• Maintain an array dist[v]: best known distance from source to node v.
• Start with dist[source] = 0 and all others as∞.
• Use a priority queue (min-heap) to always expand the node with minimal tentative distance.
• Once a node is taken out of the priority queue, its shortest distance is finalized.

2.3 Data Structures Used

• Adjacency list to store the graph efficiently.
• Distance array: dist[v] for every node.
• Predecessor array: prev[v] to reconstruct paths.
• Priority Queue (Min-Heap): to pick the next best node.

2.4 Complexity

• Using a simple array / linear search: O(V²)
• Using a min-heap (binary heap): O(E log V) – preferred for sparse graphs.

3.1 Step-by-Step Logic

1. Initialization:
   For every node v, set dist[v] = ∞ andprev[v] = NULL. Set dist[source] = 0.
2. Insert source in priority queue:
   Push the pair (0, source) into the min-heap.
3. Pick node with minimum distance:
   Extract the node u from the priority queue with the smallest dist[u].
4. Relax neighbors:
   For each neighbor v of u, check if going through u is better:
   alt = dist[u] + w(u, v)
   If alt < dist[v], update:
   dist[v] = alt and prev[v] = u; pushv into the queue.
5. Repeat:
   Continue until the priority queue is empty (all reachable nodes processed) or until you have extracted the destination node.
6. Path Reconstruction:
   To get the shortest path to some target t, followprev[t] backwards until the source is reached.

3.2 Pseudocode

DIJKSTRA(G, source):
    for each vertex v in G:
        dist[v] = ∞
        prev[v] = NULL

    dist[source] = 0
    PQ = empty min-priority-queue
    PQ.insert(source, 0)

    while PQ is not empty:
        u = PQ.extract_min()

        if u is already visited:
            continue
        mark u as visited

        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                PQ.insert(v, alt)

    return dist, prev

Note: if the graph has negative edge weights, use algorithms likeBellman–Ford instead of Dijkstra.

Real-World Use Cases

• GPS Navigation: Find the shortest driving route between two locations on a map.
• Computer Networks: Link-state routing protocols (e.g. OSPF) compute least-cost paths between routers.
• Robotics: Robots use it for path planning to avoid obstacles and minimize distance or time.
• Video Games: NPC movement and AI pathfinding in grid-based maps.
• Public Transport Planning: Minimum travel time routes across transport networks.

Advantages

• Guarantees shortest path for non-negative weights.
• Efficient for sparse graphs with a priority queue.
• Can compute shortest paths to all nodes in a single run.

Limitations

• Does not handle negative edge weights.
• Not ideal for dynamic graphs where weights change frequently.
• Explores more nodes than necessary if only a single target is needed.

7.1 Python Implementation (Adjacency List + Heap)

import heapq

def dijkstra(graph, source):
    """
    graph: adjacency list
           graph[u] = list of (v, weight)
    """
    n = len(graph)
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n

    dist[source] = 0
    pq = [(0, source)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue

        for v, w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heapq.heappush(pq, (alt, v))

    return dist, prev

7.2 C++ Implementation (Adjacency List + Priority Queue)

#include <bits/stdc++.h>
using namespace std;

void dijkstra(int n, vector<vector<pair<int,int>>> &graph, int source) {
    const int INF = 1e9;
    vector<int> dist(n, INF), parent(n, -1);
    dist[source] = 0;

    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;

    pq.push({0, source});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : graph[u]) {
            int alt = dist[u] + w;
            if (alt < dist[v]) {
                dist[v] = alt;
                parent[v] = u;
                pq.push({alt, v});
            }
        }
    }

    // dist[i] contains shortest distance from source to i
}

8.1 Scope

• Take a weighted graph as input.
• Allow the user to select a source node.
• Compute shortest distances to all nodes using Dijkstra.
• Display distances and reconstructed paths.
• Visualize algorithm behaviour on a grid.

8.2 Functional Requirements

• Input: number of nodes, edges, edge weights.
• Input: source node.
• Process: run Dijkstra and store dist[], prev[].
• Output: shortest distance and path for each node.

8.3 Non-Functional Requirements

• Correctness for all graphs with non-negative weights.
• Time: approximately O(E log V) for sparse graphs.
• Usability: clear interface and understandable outputs.
• Portability: works on typical OS platforms.

8.4 Use Case (Shortest Path)

• User enters graph and source node.
• System runs Dijkstra and computes shortest paths.
• System displays distances and path sequences.
• Optional: visualize the search process (as in this website).