Introduction

Dijkstra’s Algorithm is a popular algorithm used to find the shortest path between nodes in a graph. Named after Dutch computer scientist Edsger Dijkstra, this algorithm is widely used in networking, mapping, and various applications requiring pathfinding. This blog post will break down the algorithm into simple terms, using diagrams, tables, and mind maps, and provide implementations in both Java and Python.

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. This means it finds the shortest path from a source node to all other nodes in the graph.

Key Concepts:

• Graph: A collection of nodes (vertices) connected by edges.
• Path: A sequence of edges that connects two nodes.
• Weight: A value representing the cost of traversing an edge.
• Shortest Path: The path between two nodes with the minimum total weight.

How Dijkstra’s Algorithm Works

The algorithm uses a priority queue to repeatedly select the node with the smallest known distance, updating the distances to its neighbors as it proceeds.

Steps:

1. Initialization:
   • Set the distance to the source node to 0 and to all other nodes to infinity.
   • Set the source node as the current node.
2. Visit Neighbors:
   • For the current node, consider all its unvisited neighbors and calculate their tentative distances.
   • Update the neighbor’s distance if the calculated tentative distance is smaller.
3. Select Next Node:
   • Mark the current node as visited.
   • Select the unvisited node with the smallest tentative distance as the new current node.
4. Repeat:
   • Repeat steps 2 and 3 until all nodes have been visited or the smallest tentative distance among unvisited nodes is infinity.
5. Construct the Shortest Path:
   • The algorithm terminates when the shortest path to all nodes is determined.

Visualization:

Example with Diagram

Consider the following graph:

The graph has nodes A, B, C, D, and E, with the following edges and weights:

• A to B: 1
• A to C: 4
• B to C: 2
• B to D: 5
• C to D: 1
• D to E: 3

Step-by-Step Execution:

1. Initialization:
   • Distance: {A: 0, B: ∞, C: ∞, D: ∞, E: ∞}
   • Current node: A
2. Visit Neighbors:
   • From A: Update B to 1 and C to 4.
   • Distance: {A: 0, B: 1, C: 4, D: ∞, E: ∞}
   • Current node: B
3. Visit Neighbors:
   • From B: Update C to 3 and D to 6.
   • Distance: {A: 0, B: 1, C: 3, D: 6, E: ∞}
   • Current node: C
4. Visit Neighbors:
   • From C: Update D to 4.
   • Distance: {A: 0, B: 1, C: 3, D: 4, E: ∞}
   • Current node: D
5. Visit Neighbors:
   • From D: Update E to 7.
   • Distance: {A: 0, B: 1, C: 3, D: 4, E: 7}
   • Current node: E
6. All nodes visited: The shortest path from A to all other nodes is determined.

Implementation in Java

import java.util.*;

class Dijkstra {
    static class Node implements Comparator<Node> {
        public int node;
        public int cost;

        public Node() {}
        public Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compare(Node node1, Node node2) {
            return Integer.compare(node1.cost, node2.cost);
        }
    }

    public void dijkstra(int[] distances, List<List<Node>> graph, int source) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Node());
        pq.add(new Node(source, 0));

        distances[source] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.node;

            for (Node neighbor : graph.get(u)) {
                int v = neighbor.node;
                int weight = neighbor.cost;

                if (distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.add(new Node(v, distances[v]));
                }
            }
        }
    }

    public static void main(String[] args) {
        int vertices = 5;
        List<List<Node>> graph = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(0).add(new Node(1, 1));
        graph.get(0).add(new Node(2, 4));
        graph.get(1).add(new Node(2, 2));
        graph.get(1).add(new Node(3, 5));
        graph.get(2).add(new Node(3, 1));
        graph.get(3).add(new Node(4, 3));

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

        Dijkstra dijkstra = new Dijkstra();
        dijkstra.dijkstra(distances, graph, 0);

        System.out.println("Shortest distances from source node:");
        for (int i = 0; i < vertices; i++) {
            System.out.println("Node " + i + " is at distance " + distances[i]);
        }
    }
}

Implementation in Python

import heapq

def dijkstra(graph, source):
    distances = {node: float('infinity') for node in graph}
    distances[source] = 0
    priority_queue = [(0, source)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2, 'D': 5},
    'C': {'D': 1},
    'D': {'E': 3},
    'E': {}
}

distances = dijkstra(graph, 'A')

print("Shortest distances from source node:")
for node, distance in distances.items():
    print(f"Node {node} is at distance {distance}")

Conclusion

Dijkstra’s Algorithm is a powerful tool for finding the shortest path in a graph. By understanding its key concepts and steps, you can effectively implement it in various programming languages. With the provided Java and Python implementations, you have a practical foundation to explore this algorithm further. Happy coding!