Dijkstra's Algorithm

Dijkstra's algorithm is a fundamental algorithm in computer science, used to find the shortest path between two nodes in a graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956. This algorithm is widely used in various applications, such as network routing protocols, GPS navigation systems, and more.

In this blog, we'll explore the concept of Dijkstra's algorithm, its working, and provide code examples in Python, C++, and Java.

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. The algorithm maintains a set of vertices whose shortest paths from the source have already been determined. It iteratively selects the vertex with the minimum distance from the source, updates the distances of its adjacent vertices, and repeats the process until all vertices have been processed.

Key Features of Dijkstra's Algorithm

1. Works Only on Graphs with Non-Negative Weights:

Dijkstra's algorithm assumes that all edge weights are non-negative. If negative weights are present, the algorithm may produce incorrect results.

2. Greedy Approach:

The algorithm always selects the node with the smallest tentative distance, making it a greedy algorithm.

3. Efficient Implementation:

It can be implemented using a priority queue (min-heap) for efficient extraction of the node with the smallest distance.

4. Time Complexity:

O(V²) when using an adjacency matrix.
O((V + E) log V) when using a priority queue (min-heap), where V is the number of vertices and E is the number of edges.

How Does Dijkstra's Algorithm Work?

1. Initialization:

Set the distance of the source node to 0 and the distances of all other nodes to infinity.
Create a priority queue (min-heap) to store nodes based on their distances.

2. Processing:

Extract the node with the minimum distance from the priority queue.
For each neighbor of the extracted node, calculate the tentative distance.
If the tentative distance is less than the current known distance, update the distance and add the neighbor to the priority queue.

3. Termination:

The algorithm terminates when the priority queue is empty, meaning all nodes have been processed.

Applications of Dijkstra's Algorithm

1. Navigation Systems:

Used in GPS routing (e.g., Google Maps) to find the shortest path between two locations.

2. Network Routing:

Used in computer networks to determine the shortest path for data packets.

3. Pathfinding in AI:

Used in games and robotics for pathfinding and obstacle avoidance.

4. Project Management:

Used in the Critical Path Method (CPM) to determine the longest path in a project schedule.

Limitations of Dijkstra's Algorithm

1. Fails with Negative Weight Edges:

Dijkstra's algorithm does not work correctly if the graph contains negative edge weights. In such cases, algorithms like Bellman-Ford should be used.

2. Not Ideal for Dense Graphs:

For dense graphs (where E ≈ V²), Dijkstra's algorithm may not be the most efficient. Algorithms like Floyd-Warshall are better suited.

Code Examples

Python

import heapq

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

    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

# Example usage
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))

C++

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef pair<int, int> pii;

void dijkstra(vector<vector<pii>>& graph, int start, vector<int>& distances) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    distances[start] = 0;

    while (!pq.empty()) {
        int current_distance = pq.top().first;
        int current_node = pq.top().second;
        pq.pop();

        if (current_distance > distances[current_node]) {
            continue;
        }

        for (auto& neighbor : graph[current_node]) {
            int neighbor_node = neighbor.first;
            int weight = neighbor.second;
            int distance = current_distance + weight;

            if (distance < distances[neighbor_node]) {
                distances[neighbor_node] = distance;
                pq.push({distance, neighbor_node});
            }
        }
    }
}

int main() {
    int nodes = 4;
    vector<vector<pii>> graph(nodes);
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({0, 1});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 5});
    graph[2].push_back({0, 4});
    graph[2].push_back({1, 2});
    graph[2].push_back({3, 1});
    graph[3].push_back({1, 5});
    graph[3].push_back({2, 1});

    vector<int> distances(nodes, INT_MAX);
    dijkstra(graph, 0, distances);

    for (int i = 0; i < nodes; i++) {
        cout << "Distance from 0 to " << i << " is " << distances[i] << endl;
    }

    return 0;
}

Java

import java.util.*;

public class Dijkstra {
    static class Edge {
        int node, weight;
        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    public static void dijkstra(List<List<Edge>> graph, int start, int[] distances) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(start, 0));
        distances[start] = 0;

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.node;
            int currentDistance = current.weight;

            if (currentDistance > distances[currentNode]) {
                continue;
            }

            for (Edge neighbor : graph.get(currentNode)) {
                int neighborNode = neighbor.node;
                int weight = neighbor.weight;
                int distance = currentDistance + weight;

                if (distance < distances[neighborNode]) {
                    distances[neighborNode] = distance;
                    pq.add(new Edge(neighborNode, distance));
                }
            }
        }
    }

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

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

        int[] distances = new int[nodes];
        Arrays.fill(distances, Integer.MAX_VALUE);
        dijkstra(graph, 0, distances);

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