Dijkstra’s Algorithm Explanation with example

In the world of computer science and graph theory, Dijkstra’s Algorithm is one of the most famous and widely used algorithms to find the shortest path between nodes in a graph. Dijkstra’s algorithm, given by a brilliant Dutch computer scientist and software engineer Dr. Edsger Dijkstra in 1959. Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed and undirected graph that has non-negative edge weight.

Dijkstra’s Algorithm works for both directed and undirected graphs, as long as all edge weights are non-negative.

How It Works for Both Graphs?

• Undirected Graph: Each edge is treated as bidirectional. For example, if there is an edge between A and B with weight 2, the algorithm considers you can go from A → B and from B → A, both with weight 2.
• Directed Graph: Each edge has a specific direction. If there’s an edge from A → B with weight 2, but no edge from B → A, then you can only travel from A to B, not the other way around.

Statement

For Graph G = (V,E)
w (u, v) ≥ 0 for each edge (u, v) ∈ E.

Means: “In the graph G, for every connection (edge) between nodes u and v, the weight (or cost) must be zero or positive.”

Explanation:

1. G = (V, E)

This is the mathematical representation of a graph:

• V = the set of vertices (nodes)
• E = the set of edges (connections between nodes)

So, G = (V,E) means the graph is made up of:

• A list of nodes (like cities or people), and
• A list of edges (like roads or relationships) that connect those nodes.

2. w(u, v)

This is the weight function.
It gives the weight or cost of traveling from node u to node v via edge (u, v).

For example:

• If u = A and v = B and w(A, B) = 5, it means there’s a path from A to B with a cost/weight of 5.

3. w(u, v) ≥ 0

This means the weight of every edge is non-negative.

• It cannot be negative (i.e., no edge can have a cost like -3).
• It can be zero or positive (i.e., 0, 1, 5, 100, etc.).

4. (u, v) ∈ E

This means the condition applies to all edges in the graph.

Limitation of Dijkstra’s Algorithm?

Dijkstra’s Algorithm only works when all edge weights are non-negative. If even one edge has a negative weight, Dijkstra’s logic can fail to find the correct shortest path. That’s why this condition w(u, v) ≥ 0 is a requirement for applying Dijkstra’s Algorithm.

Example of Dijkstra’s Algorithm

Problem

We want to find the shortest distance from one source node to all other nodes in a graph with non-negative weights.

Example Graph

• 5 cities (nodes): A (0), B (1), C (2), D (3), E (4)
• Roads (edges with distances):
  • A → B = 4
  • A → C = 2
  • B → C = 5
  • B → D = 10
  • C → E = 3
  • E → D = 4

Goal

Find the shortest distance from A to every other city using Dijkstra’s Algorithm.

Steps to Find the shortest Distance

• Start at A (source):
  • Distance to itself = 0.
  • Distances to others = ∞ (unknown yet).

A=0, B=∞, C=∞, D=∞, E=∞

• From A, check neighbors:
  • A → B = 4 → update B = 4.
  • A → C = 2 → update C = 2.

A=0, B=4, C=2, D=∞, E=∞

Pick the smallest unvisited: C (2).

• From C, check neighbors:
  • C → E = 3 → A→C (2) + C→E (3) = 5 → update E = 5.
  • C → B = 5 → A→C (2) + C→B (5) = 7 (but current B=4, so no update).

A=0, B=4, C=2, D=∞, E=5

Next smallest unvisited: B (4).

• From B, check neighbors:
  • B → D = 10 → A→B (4) + 10 = 14 → update D = 14.
  • B → C = 5, but C is already shorter (2).

A=0, B=4, C=2, D=14, E=5

Next smallest unvisited: E (5).

• From E, check neighbors:
  • E → D = 4 → A→E (5) + 4 = 9 → update D = 9 (better than 14).

A=0, B=4, C=2, D=9, E=5

Next smallest unvisited: D (9).

• From D, check neighbors:
  • Nothing shorter is found.

Final Shortest Distances from A

• A → A = 0
• A → B = 4
• A → C = 2
• A → D = 9
• A → E = 5

Dijkstra’s Algorithm

1. Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest-path tree, i.e., whose minimum distance from the source is calculated and finalized. Initially, this set is empty.
2. Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3. While sptSet doesn’t include all vertices
   • Pick a vertex u which is not there in sptSet and has a minimum distance value.
   • Include u to sptSet.
   • Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the sum of a distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

How Dijkstra’s Algorithm Works

Here’s a step-by-step explanation:

1. Start at the source node and set its distance to 0. Set all other nodes’ distances to infinity (∞).
2. Maintain a priority queue (or min-heap) of unvisited nodes, prioritized by the smallest known distance.
3. At each step:
   • Pick the node with the smallest known distance.
   • For each unvisited neighbor:
     • Calculate new distance = current node’s distance + edge weight.
     • If this new distance is less than the previously recorded distance, update it.
4. Mark the current node as visited.
5. Repeat until all nodes are visited or the shortest path to the destination is found.

Pseudocode of Dijkstra’s Algorithm

function Dijkstra(Graph, source):
    create distance[] and set all values to infinity
    distance[source] = 0
    create a min-priority queue and add source
    
    while queue is not empty:
        current = extract_min(queue)
        
        for neighbor in current.neighbors:
            temp_dist = distance[current] + weight(current, neighbor)
            
            if temp_dist < distance[neighbor]:
                distance[neighbor] = temp_dist
                update priority queue with new distance

    return distance[]

Optimized Version: Using Priority Queue

Problem with the normal approach

• In the regular Dijkstra, to pick the next closest node, we look at all unvisited nodes and find the one with the smallest distance.
• If there are many nodes, this takes a lot of time (O(V²)).

Using a PriorityQueue greatly improves performance (from O(V²) to O((V+E) log V)).

How Priority Queue helps

• A Priority Queue is like a “smart waiting line” where the node with the smallest distance always comes out first.
• This means we don’t need to scan all nodes every time to find the closest one.
• When we update a neighbor’s distance, we add it to the queue. The queue automatically keeps it in the right order.

Lets see an example to understand Dijkstra’s Algorithm

Below is a directed weighted graph. We will find shortest path between all the vertices using Dijkstra’a Algorithm.

Java Code to Implement Dijkstra’s Algorithm

import java.util.*;

public class DijkstraExample {
    static class Edge {
        int target, weight;
        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    public static void dijkstra(List<List<Edge>> graph, int source) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int currentDist = current[1];

            for (Edge edge : graph.get(node)) {
                int neighbor = edge.target;
                int newDist = currentDist + edge.weight;

                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{neighbor, newDist});
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println("Distance from " + source + " to " + i + " is " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int n = 5; // number of nodes
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // add edges: graph.get(u).add(new Edge(v, weight));
        graph.get(0).add(new Edge(1, 1)); // A to B
        graph.get(0).add(new Edge(3, 4)); // A to D
        graph.get(1).add(new Edge(2, 3)); // B to C
        graph.get(1).add(new Edge(4, 2)); // B to E
        graph.get(3).add(new Edge(4, 1)); // D to E

        dijkstra(graph, 0); // source is node 0 (A)
    }
}

Time and Space Complexity of Dijkstra’s Algorithm

Time Complexity

Implementation	Time Complexity
Naive (Simple array)	O(V²)
Using Priority Queue (Min-Heap)	O((V + E) log V)

Space Complexity

Implementation	Space Complexity
Naive (Simple array)	O(V)
Using Priority Queue (Min-Heap)	O(V + E)

When to Use Dijkstra’s Algorithm

Use Dijkstra’s Algorithm when:

• You want to find the shortest path from a single source to all other nodes.
• Your graph contains non-negative weights.
• The graph is sparse or large, and you want efficiency.

Real-Life Applications of Dijkstra’s Algorithm

• GPS systems (Google Maps, Uber)
• To find the shortest path between source and destination
• Network packet routing (OSPF in networking)
• AI in games for pathfinding (e.g., enemy chase logic)
• In social networking applications to map the connections and information
• In networking to route the data

Disadvantage of Dijkstra’s Algorithm

• It follows the blind search, so wastes a lot of time to give the desired output.
• It Negative edges value cannot be handled by it.
• We need to keep track of vertices that have been visited.

Comparison with Other Algorithms

Algorithm	Handles Negative Weights	Complexity	Best Use Case
Dijkstra	No	O((V + E) log V)	Fastest on non-negative graphs
Bellman-Ford	Yes	O(V * E)	Graphs with negative weights
A*	No (unless heuristics handle it)	Depends on heuristic	Pathfinding with prediction
Floyd-Warshall	Yes	O(V³)	All-pairs shortest paths

FAQs and Interview Questions

• Can Dijkstra’s Algorithm be used for negative weights?
  No, use Bellman-Ford for that.
• Why use PriorityQueue in Dijkstra?
  To optimize the selection of the minimum distance node.
• Can Dijkstra find all shortest paths from one node?
  Yes, to all nodes with non-negative weights.
• What is the time complexity with a min-heap?
  O((V + E) log V)