Dijkstra Algorithm is used to find the shortest path from a source node to all other nodes in a weighted graph where weights are non-negative.

Key Points (Quick Revision)

• Finds the shortest path
• Works on weighted graphs
• Does NOT work with negative weights
• Uses Priority Queue (Min Heap)
• Time Complexity: O((V + E) log V)

Dijkstra in Simple Words

• Start from one node
• Find the closest node
• Then the next closest
• Continue until all nodes are covered

It always chooses the minimum distance first.

Real-Life Example

Think about Google Maps:

• You start from your location
• It finds the shortest path to the destination
• It checks multiple routes
• Chooses the minimum distance

That’s the Dijkstra Algorithm.

Example Graph

     (4)
  A ------- B
  |         |
 (2)       (5)
  |         |
  C ------- D
      (1)

Shortest path from A:

• A → C → D → B

How Dijkstra Works (Step-by-Step)

1. Set all distances = infinity
2. Distance of source = 0
3. Pick the node with the smallest distance
4. Update neighbors’ distance
5. Repeat

Algorithm (Simple Version)

Start from source
→ Set distance = 0
→ Use priority queue
→ Pick smallest distance node
→ Update neighbors
→ Repeat

Java Code – Dijkstra Algorithm

import java.util.*;

class Pair {
    int node, distance;

    Pair(int node, int distance) {
        this.node = node;
        this.distance = distance;
    }
}

public class Dijkstra {

    int vertices;
    List<List<Pair>> graph;

    public Dijkstra(int v) {
        vertices = v;
        graph = new ArrayList<>();

        for (int i = 0; i < v; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v, int weight) {
        graph.get(u).add(new Pair(v, weight));
        graph.get(v).add(new Pair(u, weight));
    }

    public void dijkstra(int src) {

        PriorityQueue<Pair> pq = new PriorityQueue<>(
            (a, b) -> a.distance - b.distance
        );

        int[] dist = new int[vertices];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[src] = 0;
        pq.add(new Pair(src, 0));

        while (!pq.isEmpty()) {

            Pair current = pq.poll();

            for (Pair neighbor : graph.get(current.node)) {

                int newDist = current.distance + neighbor.distance;

                if (newDist < dist[neighbor.node]) {
                    dist[neighbor.node] = newDist;
                    pq.add(new Pair(neighbor.node, newDist));
                }
            }
        }

        // Print result
        System.out.println("Shortest distances from source:");
        for (int i = 0; i < vertices; i++) {
            System.out.println("Node " + i + " → " + dist[i]);
        }
    }

    public static void main(String[] args) {

        Dijkstra g = new Dijkstra(4);

        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 2);
        g.addEdge(2, 3, 1);
        g.addEdge(1, 3, 5);

        g.dijkstra(0);
    }
}

When to Use Dijkstra

Use Dijkstra when:

✔ Graph is weighted
✔ You need the shortest path
✔ No negative weights
✔ You want efficient path finding

Applications of Dijkstra

• Google Maps
• GPS navigation
• Network routing
• Flight systems
• Delivery optimization

BFS vs Dijkstra

FAQ – Quick Answers

What is the Dijkstra Algorithm?

Dijkstra’s algorithm is used to find the shortest path in a weighted graph.

What data structure is used in Dijkstra?

Priority Queue (Min Heap)

Can Dijkstra handle negative weights?

No, it does not support negative weights.

What is time complexity of Dijkstra?

O((V + E) log V)