Dijkstra's Algorithm
Description
Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. For a given source node in the graph, the algorithm finds the shortest path between that node and every other node.
History
Dijkstra's algorithm was developed by Dutch computer scientist Edsger Dijkstra in 1956. It is a fundamental algorithm in computer science, used for finding the shortest paths between all pairs of vertices in a weighted graph. The algorithm works by incrementally improving an estimate on the shortest path between two vertices by considering if using an intermediate vertex would create a shorter path. The algorithm was conceived by Dijkstra in 1956 while having coffee in Rotterdam, where he was trying to demonstrate the capabilities of the new ARMAC computer. He needed a problem that was easily understood to showcase the machine's abilities, and decided on finding the shortest path between two cities in the Netherlands. He designed what is now known as Dijkstra's algorithm and implemented it for a slightly simplified transportation map with 64 cities. The algorithm was published in 1959 in a three-page paper titled "A Note on Two Problems in Connexion with Graphs". This publication is considered one of the most influential papers in computer science, and the algorithm remains widely used today in routing protocols, GPS systems, social networks, and many other applications requiring shortest path calculations.
How It Works
- Initialize distances to all vertices as infinite and distance to the source as 0
- Create a set of unvisited nodes containing all nodes
- For the current node (initially the source):
- Calculate tentative distances to all unvisited neighbors
- If the calculated distance is less than the previously recorded distance, update it
- Mark the current node as visited
- Select the unvisited node with the smallest tentative distance as the new current node
- Repeat step 3 until all nodes are visited
Visualization
Select source node
Implementation
from heapq import heappush, heappop
from collections import defaultdict
import math
def dijkstra(graph, start):
# Initialize distances and previous nodes
distances = {node: math.inf for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
# Priority queue to store (distance, node)
pq = [(0, start)]
while pq:
current_distance, current = heappop(pq)
# If we've found a longer path, skip
if current_distance > distances[current]:
continue
# Check all neighbors of current node
for neighbor, weight in graph[current].items():
distance = current_distance + weight
# If we've found a shorter path, update it
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heappush(pq, (distance, neighbor))
return distances, previous
# Example usage
if __name__ == "__main__":
# Example graph represented as adjacency list with weights
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
'D': {'B': 5, 'C': 8, 'E': 2},
'E': {'C': 10, 'D': 2}
}
start_node = 'A'
distances, previous = dijkstra(graph, start_node)
print(f"Shortest distances from {start_node}:")
for node, distance in distances.items():
print(f"{node}: {distance}")
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
class DijkstraAlgorithm {
private:
using Graph = std::unordered_map<char, std::unordered_map<char, int>>;
static void printPath(const std::vector<char>& path) {
for (size_t i = 0; i < path.size(); ++i) {
std::cout << path[i];
if (i < path.size() - 1) std::cout << " -> ";
}
std::cout << std::endl;
}
public:
static std::pair<std::unordered_map<char, int>, std::unordered_map<char, char>>
findShortestPaths(const Graph& graph, char start) {
std::unordered_map<char, int> distances;
std::unordered_map<char, char> previous;
// Initialize distances
for (const auto& node : graph) {
distances[node.first] = std::numeric_limits<int>::max();
}
distances[start] = 0;
// Priority queue of (distance, node)
std::priority_queue<std::pair<int, char>,
std::vector<std::pair<int, char>>,
std::greater<std::pair<int, char>>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [currentDist, current] = pq.top();
pq.pop();
// Skip if we've found a better path
if (currentDist > distances[current]) continue;
// Check all neighbors
for (const auto& [neighbor, weight] : graph.at(current)) {
int distance = currentDist + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
previous[neighbor] = current;
pq.push({distance, neighbor});
}
}
}
return {distances, previous};
}
static std::vector<char> reconstructPath(
const std::unordered_map<char, char>& previous,
char start,
char end
) {
std::vector<char> path;
char current = end;
while (current != start) {
path.push_back(current);
if (previous.find(current) == previous.end()) {
return {}; // No path exists
}
current = previous.at(current);
}
path.push_back(start);
std::reverse(path.begin(), path.end());
return path;
}
};
// Example usage
int main() {
DijkstraAlgorithm::Graph graph = {
{'A', {{'B', 4}, {'C', 2}}},
{'B', {{'A', 4}, {'C', 1}, {'D', 5}}},
{'C', {{'A', 2}, {'B', 1}, {'D', 8}, {'E', 10}}},
{'D', {{'B', 5}, {'C', 8}, {'E', 2}}},
{'E', {{'C', 10}, {'D', 2}}}
};
char start = 'A';
char end = 'E';
auto [distances, previous] = DijkstraAlgorithm::findShortestPaths(graph, start);
std::cout << "Shortest distances from " << start << ":\n";
for (const auto& [node, distance] : distances) {
std::cout << node << ": " << distance << std::endl;
}
std::cout << "\nShortest path from " << start << " to " << end << ":\n";
auto path = DijkstraAlgorithm::reconstructPath(previous, start, end);
DijkstraAlgorithm::printPath(path);
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
public class DijkstraAlgorithm
{
private class PriorityQueue<T>
{
private SortedDictionary<int, Queue<T>> _dictionary = new();
public void Enqueue(int priority, T item)
{
if (!_dictionary.ContainsKey(priority))
_dictionary[priority] = new Queue<T>();
_dictionary[priority].Enqueue(item);
}
public T Dequeue()
{
var first = _dictionary.First();
var result = first.Value.Dequeue();
if (!first.Value.Any())
_dictionary.Remove(first.Key);
return result;
}
public bool Any() => _dictionary.Any();
}
public static (Dictionary<char, int> distances, Dictionary<char, char> previous)
FindShortestPaths(Dictionary<char, Dictionary<char, int>> graph, char start)
{
var distances = new Dictionary<char, int>();
var previous = new Dictionary<char, char>();
var pq = new PriorityQueue<char>();
// Initialize distances
foreach (var node in graph.Keys)
{
distances[node] = int.MaxValue;
}
distances[start] = 0;
pq.Enqueue(0, start);
while (pq.Any())
{
var current = pq.Dequeue();
foreach (var neighbor in graph[current])
{
var distance = distances[current] + neighbor.Value;
if (distance < distances[neighbor.Key])
{
distances[neighbor.Key] = distance;
previous[neighbor.Key] = current;
pq.Enqueue(distance, neighbor.Key);
}
}
}
return (distances, previous);
}
public static List<char> ReconstructPath(
Dictionary<char, char> previous,
char start,
char end)
{
var path = new List<char>();
var current = end;
while (current != start)
{
path.Add(current);
if (!previous.ContainsKey(current))
return new List<char>(); // No path exists
current = previous[current];
}
path.Add(start);
path.Reverse();
return path;
}
private static void PrintPath(List<char> path)
{
Console.WriteLine(string.Join(" -> ", path));
}
// Example usage
public static void Main()
{
var graph = new Dictionary<char, Dictionary<char, int>>
{
['A'] = new Dictionary<char, int> { ['B'] = 4, ['C'] = 2 },
['B'] = new Dictionary<char, int> { ['A'] = 4, ['C'] = 1, ['D'] = 5 },
['C'] = new Dictionary<char, int> { ['A'] = 2, ['B'] = 1, ['D'] = 8, ['E'] = 10 },
['D'] = new Dictionary<char, int> { ['B'] = 5, ['C'] = 8, ['E'] = 2 },
['E'] = new Dictionary<char, int> { ['C'] = 10, ['D'] = 2 }
};
char start = 'A';
char end = 'E';
var (distances, previous) = FindShortestPaths(graph, start);
Console.WriteLine($"Shortest distances from {start}:");
foreach (var (node, distance) in distances)
{
Console.WriteLine($"{node}: {distance}");
}
Console.WriteLine($"\nShortest path from {start} to {end}:");
var path = ReconstructPath(previous, start, end);
PrintPath(path);
}
}
Advantages and Disadvantages
Advantages
- Finds the optimal (shortest) path
- Works with any graph with non-negative weights
- Efficient for sparse graphs
Disadvantages
- Doesn't work with negative weights
- Can be slow for dense graphs
- Requires all edge weights to be known