Dijkstra's Algorithm

History of Dijkstra's Algorithm

Edsger W. Dijkstra developed this algorithm in 1956 while thinking about how to demonstrate the capabilities of the new ARMAC computer in Amsterdam. Interestingly, he designed it in about 20 minutes while having coffee at a café. The algorithm was published in 1959. At the time, this was considered a breakthrough in computing as it provided an efficient way to solve the shortest path problem. Dijkstra originally designed it to find the shortest path between two cities in the Netherlands, a practical application that showcases its real-world utility.

Fundamentals of Dijkstra's Algorithm

The algorithm works on the principle of relaxation, where an approximation to the correct distance is gradually replaced by more accurate values until the shortest path is reached. It maintains two sets of vertices: visited and unvisited. It starts from a source vertex, initially marks all vertices as unvisited and sets their tentative distances to infinity except for the source vertex (which gets a value of 0). As the algorithm processes each vertex, it marks it as visited and updates the tentative distances to all its unvisited neighbors.

Need for Dijkstra’s Algorithm (Purpose and Use-Cases)

• Routing in Networks: Optimizes the path for data transmission in communication networks.
• GPS Systems: Determines the shortest route between locations in navigation software.
• Robotics: Helps robots plan the shortest path in obstacle-filled environments.
• Telecommunications: Used to find the best route for data across networks to minimize delays.

Can Dijkstra’s Algorithm work on both Directed and Undirected Graphs?

Yes, Dijkstra’s Algorithm can work on both directed and undirected graphs. In directed graphs, edges have a direction (from one node to another), while in undirected graphs, edges have no direction, meaning the path can be traversed in both directions.

Algorithm for Dijkstra's Algorithm

1. Initialize all vertices with distance infinity except the source vertex (distance = 0)
2. Create a set of unvisited vertices containing all vertices
3. For each iteration, select the unvisited vertex with a minimum distance value
4. Mark the selected vertex as visited
5. Update the distances of all adjacent unvisited vertices
6. If the new calculated distance is less than the previous distance, update it
7. Repeat until all vertices are visited
8. The final distances represent the shortest paths from the source to all vertices

Dijkstra's Algorithm Applications

• Network Routing Protocols: Used in OSPF (Open Shortest Path First) protocol
• Maps and Navigation Systems: Implemented in GPS devices and mapping software
• Social Networks: Finding the shortest connection paths between users
• Telephone Networks: Routing calls through the network efficiently
• Games Development: Pathfinding in video games
• Biology: Modeling protein-protein interaction networks
• Operations Research: Supply chain optimization and logistics
• Urban Planning: Traffic flow optimization and city planning

How does Dijkstra’s Algorithm work?

• Initialization: Set the distance of the start node as 0 and all others as infinity.
• Node Selection: Select the unvisited node with the smallest tentative distance.
• Distance Update: Update the tentative distances of neighboring nodes.
• Repetition: Repeat the process until all nodes are visited.

Pseudo Code for Dijkstra’s Algorithm

1. Initialize distance of source node to 0
2. Initialize distance of all other nodes to infinity
3. Set all nodes as unvisited
4. While there are unvisited nodes:
   a. Select the unvisited node with the smallest distance
   b. For each unvisited neighbor, calculate the tentative distance
   c. Update the neighbor’s distance if a shorter path is found
   d. Mark the current node as visited
5. Repeat until all nodes are visited
6. Return the shortest distances

Implementation of Dijkstra's Algorithm

• Python

Python

from collections import defaultdict
import heapq

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # Remove this line for directed graph
    
    def dijkstra(self, src):
        # Initialize distances with infinity for all vertices
        distances = {vertex: float('infinity') for vertex in self.graph}
        distances[src] = 0
        
        # Priority queue to store vertices and their distances
        pq = [(0, src)]
        
        # Dictionary to store the shortest path
        previous = {vertex: None for vertex in self.graph}
        
        while pq:
            # Get vertex with minimum distance
            current_distance, current_vertex = heapq.heappop(pq)
            
            # If we found a longer path, skip
            if current_distance > distances[current_vertex]:
                continue
                
            # Check all adjacent vertices
            for neighbor, weight in self.graph[current_vertex]:
                distance = current_distance + weight
                
                # If we found a shorter path
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current_vertex
                    heapq.heappush(pq, (distance, neighbor))
        
        return distances, previous

# Example usage
g = Graph()
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 2)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 5)
g.add_edge(2, 3, 8)
g.add_edge(2, 4, 10)
g.add_edge(3, 4, 2)

source = 0
distances, previous = g.dijkstra(source)

print(f"Distances from source {source}:")
for vertex in distances:
    print(f"Vertex {vertex}: {distances[vertex]}")

print("\nShortest paths:")
for vertex in previous:
    path = []
    current = vertex
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    print(f"Path to vertex {vertex}: {' -> '.join(map(str, path))}")

You can also try this code with Online Python Compiler

Run Code

Implementation of Dijkstra's Algorithm in Different Programming Languages

• C++
• Java
• JS

C++

#include <vector>
#include <queue>
#include <limits>
using namespace std;

class Graph {
    int V;
    vector<vector<pair<int, int>>> adj;
    
public:
    Graph(int V) : V(V) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight});
    }
    
    vector<int> dijkstra(int src) {
        vector<int> dist(V, numeric_limits<int>::max());
        dist[src] = 0;
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, src});
        
        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            
            for (auto& [v, weight] : adj[u]) {
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return dist;
    }
};

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.*;

class Graph {
    private int V;
    private List<List<Node>> adj;
    
    class Node implements Comparable<Node> {
        int vertex, weight;
        
        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
        
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }
    
    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());
    }
    
    void addEdge(int u, int v, int weight) {
        adj.get(u).add(new Node(v, weight));
        adj.get(v).add(new Node(u, weight));
    }
    
    void dijkstra(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(src, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            
            for (Node neighbor : adj.get(current.vertex)) {
                if (dist[current.vertex] + neighbor.weight < dist[neighbor.vertex]) {
                    dist[neighbor.vertex] = dist[current.vertex] + neighbor.weight;
                    pq.add(new Node(neighbor.vertex, dist[neighbor.vertex]));
                }
            }
        }
        
        // Print results
        for (int i = 0; i < V; i++)
            System.out.println("Distance to vertex " + i + ": " + dist[i]);
    }
}

You can also try this code with Online Java Compiler

Run Code

JS

class PriorityQueue {
    constructor() {
        this.values = [];
    }
    
    enqueue(val, priority) {
        this.values.push({val, priority});
        this.sort();
    }
    
    dequeue() {
        return this.values.shift();
    }
    
    sort() {
        this.values.sort((a, b) => a.priority - b.priority);
    }
}

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    
    addEdge(vertex1, vertex2, weight) {
        this.adjacencyList[vertex1].push({node: vertex2, weight});
        this.adjacencyList[vertex2].push({node: vertex1, weight});
    }
    
    dijkstra(start) {
        const distances = {};
        const previous = {};
        const pq = new PriorityQueue();
        
        // Initialize distances
        for (let vertex in this.adjacencyList) {
            if (vertex === start) {
                distances[vertex] = 0;
                pq.enqueue(vertex, 0);
            } else {
                distances[vertex] = Infinity;
                pq.enqueue(vertex, Infinity);
            }
            previous[vertex] = null;
        }
        
        while (pq.values.length) {
            let current = pq.dequeue().val;
            
            for (let neighbor of this.adjacencyList[current]) {
                let distance = distances[current] + neighbor.weight;
                
                if (distance < distances[neighbor.node]) {
                    distances[neighbor.node] = distance;
                    previous[neighbor.node] = current;
                    pq.enqueue(neighbor.node, distance);
                }
            }
        }
        
        return {distances, previous};
    }
}

You can also try this code with Online Javascript Compiler

Run Code

Dijkstra's Algorithm on Directed Graphs

In directed graphs, edges have a direction, meaning a node A can have a directed edge to node B, but not necessarily vice versa. Dijkstra’s Algorithm works by considering only the directed edges during the traversal and updating the shortest paths accordingly.

Example:

• Nodes: A, B, C
• Edges: A → B (weight 2), B → C (weight 1)
• Applying Dijkstra’s Algorithm will give the shortest path from A to C as A → B → C with a total weight of 3.

Returning The Paths from Dijkstra's Algorithm

In addition to finding the shortest distances, you can also track the actual path taken by maintaining a record of previous nodes. This allows you to reconstruct the shortest path once the algorithm finishes.

Example:

• Source node: A
• Path to B: A → B
• Path to C: A → B → C

Dijkstra's Algorithm with a Single Destination Vertex

Dijkstra’s Algorithm can be adapted to find the shortest path from a source node to a specific destination node by halting once the destination node is reached.

Example:

• Source: A
• Destination: C
• Path: A → B → C (shortest path from A to C)

Time Complexity for Dijkstra’s Algorithm

The time complexity of Dijkstra’s Algorithm is O(V²) using an array or O((V + E) log V) using a priority queue, where V is the number of vertices and E is the number of edges.

Example:

• With 100 vertices and 500 edges, the algorithm’s time complexity will be O(100²) or O((100 + 500) log 100).

Advantages of Dijkstra's Algorithm

• Efficient for finding the shortest path in graphs with non-negative weights.
• Guarantees the optimal solution.
• Widely applicable in real-world problems like routing and network optimization.

Disadvantages of Dijkstra's Algorithm

• Cannot handle negative weight edges.
• Requires a lot of memory and computation for dense graphs.
• Slower on large graphs without optimizations like priority queues.

Frequently Asked Questions

Can the Dijkstra Algorithm handle negative edge weights?

Dijkstra cannot handle the negative edges properly. In a few cases, it may yield the right solution, but it will fail most of the time. To properly handle negative edges, we use the Bellman-Ford algorithm.

What is the purpose of the Dijkstra Algorithm?

Dijkstra's algorithm solves the shortest-path problem for any weighted, directed graph with non-negative weights. It can handle graphs consisting of cycles, but negative weights will cause this algorithm to produce incorrect results.

Where is the Dijkstra algorithm used?

Dijkstra's algorithm is used in various fields, including GPS navigation systems, network routing protocols (like OSPF and IS-IS), robotics for pathfinding, telecommunications for optimizing data transfer routes, and in computer games for AI navigation and pathfinding.

Conclusion

Dijkstra's Algorithm is a fundamental tool in computer science, efficiently solving the shortest path problem in weighted graphs. Its practical applications in navigation, networking, and AI make it invaluable across various industries. By understanding its working mechanism and implementation, you can optimize systems that rely on route finding and cost minimization, enhancing performance and efficiency.
Recommended Problems: 

• Shortest Path In Binary Matrix
• Binary Array Sorting

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.
 

Learn various topics from Web Technologies, Programming Fundamentals, Data Structure, and Algorithms from our Library. 

Happy Coding!