Fundamentals of Dijkstra's Algorithm
- Dijkstra's Algorithm works by gradually refining the estimated shortest distance to each vertex until the final shortest path is determined. It maintains two sets of vertices: visited and unvisited.
- The algorithm starts from a source vertex, setting all other vertices' distances to infinity, except the source (set to 0). As each vertex is processed, it is marked as visited, and the tentative distances of its unvisited neighbors are updated accordingly.
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
- Initialize all vertices with distance infinity except the source vertex (distance = 0)
- Create a set of unvisited vertices containing all vertices
- For each iteration, select the unvisited vertex with a minimum distance value
- Mark the selected vertex as visited
- Update the distances of all adjacent unvisited vertices
- If the new calculated distance is less than the previous distance, update it
- Repeat until all vertices are visited
- 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
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
C++
#include <iostream>
#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});
}
void 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});
}
}
}
cout << "Vertex \t Distance from Source " << src << endl;
for (int i = 0; i < V; i++)
cout << i << "\t" << dist[i] << endl;
}
};
int main() {
Graph g(5);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 5);
g.addEdge(2, 3, 8);
g.addEdge(2, 4, 10);
g.addEdge(3, 4, 2);
g.dijkstra(0);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.*;
class Graph {
private int V;
private List<List<int[]>> adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
}
public void addEdge(int u, int v, int weight) {
adj.get(u).add(new int[]{v, weight});
adj.get(v).add(new int[]{u, weight});
}
public void dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.add(new int[]{0, src});
while (!pq.isEmpty()) {
int[] node = pq.poll();
int u = node[1];
for (int[] neighbor : adj.get(u)) {
int v = neighbor[0], weight = neighbor[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new int[]{dist[v], v});
}
}
}
System.out.println("Vertex\tDistance from Source " + src);
for (int i = 0; i < V; i++)
System.out.println(i + "\t" + dist[i]);
}
public static void main(String[] args) {
Graph g = new Graph(5);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 5);
g.addEdge(2, 3, 8);
g.addEdge(2, 4, 10);
g.addEdge(3, 4, 2);
g.dijkstra(0);
}
}
You can also try this code with Online Java Compiler
JS
class Graph {
constructor() {
this.adj = new Map();
}
addEdge(u, v, weight) {
if (!this.adj.has(u)) this.adj.set(u, []);
if (!this.adj.has(v)) this.adj.set(v, []);
this.adj.get(u).push([v, weight]);
this.adj.get(v).push([u, weight]);
}
dijkstra(src) {
let dist = new Map();
for (let key of this.adj.keys()) dist.set(key, Infinity);
dist.set(src, 0);
let pq = [[0, src]];
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]); // Min-heap using sort
let [currentDistance, u] = pq.shift();
for (let [v, weight] of this.adj.get(u)) {
let newDist = currentDistance + weight;
if (newDist < dist.get(v)) {
dist.set(v, newDist);
pq.push([newDist, v]);
}
}
}
console.log(`Vertex\tDistance from Source ${src}`);
for (let [key, value] of dist.entries()) console.log(`${key}\t${value}`);
}
}
let g = new Graph();
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 5);
g.addEdge(2, 3, 8);
g.addEdge(2, 4, 10);
g.addEdge(3, 4, 2);
g.dijkstra(0);
You can also try this code with Online Javascript Compiler
PHP
<?php
class Graph {
private $vertices;
private $adj;
public function __construct($vertices) {
$this->vertices = $vertices;
$this->adj = array_fill(0, $vertices, []);
}
public function addEdge($u, $v, $weight) {
$this->adj[$u][] = [$v, $weight];
$this->adj[$v][] = [$u, $weight];
}
public function dijkstra($src) {
$dist = array_fill(0, $this->vertices, PHP_INT_MAX);
$dist[$src] = 0;
$pq = new SplPriorityQueue();
$pq->insert([$src, 0], 0);
while (!$pq->isEmpty()) {
list($u, $currentDistance) = $pq->extract();
if ($currentDistance > $dist[$u]) continue;
foreach ($this->adj[$u] as [$v, $weight]) {
$newDist = $currentDistance + $weight;
if ($newDist < $dist[$v]) {
$dist[$v] = $newDist;
$pq->insert([$v, $newDist], -$newDist);
}
}
}
echo "Vertex\tDistance from Source $src\n";
foreach ($dist as $vertex => $distance) {
echo "$vertex\t$distance\n";
}
}
}
// Create graph and add edges
$g = new Graph(5);
$g->addEdge(0, 1, 4);
$g->addEdge(0, 2, 2);
$g->addEdge(1, 2, 1);
$g->addEdge(1, 3, 5);
$g->addEdge(2, 3, 8);
$g->addEdge(2, 4, 10);
$g->addEdge(3, 4, 2);
$g->dijkstra(0);
?>
You can also try this code with Online PHP Compiler
Output
Vertex Distance from Source 0
0 0
1 3
2 2
3 8
4 10
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.
34+ registered 
