Algorithm
Dijkstra's algorithm, named after computer scientist Edsger Dijkstra, is a graph search algorithm that finds the shortest path between two nodes in a weighted graph. The algorithm works for graphs with non-negative edge weights and is commonly used in various applications, such as network routing protocols and maps.
Here's a basic overview of how Dijkstra's algorithm works:
-
Initialization:
- Assign a tentative distance value to every node. The initial node has a distance of 0, and all other nodes are assigned a distance of infinity.
- Set the initial node as the current node.
-
Visit Neighbors:
- For the current node, consider all of its neighbors (nodes that can be reached directly from the current node).
- Calculate the tentative distance from the initial node to each neighbor through the current node.
- If the calculated distance is less than the previously assigned distance, update the distance.
-
Mark as Visited:
- After considering all neighbors of the current node, mark the current node as visited.
- A visited node will not be checked again.
-
Select Next Node:
- Choose the unvisited node with the smallest tentative distance as the next "current node" and go back to step 2.
-
Repeat:
- Repeat steps 2-4 until the destination node is marked as visited or all reachable nodes have been considered.
-
Path Reconstruction:
- Once the destination node is marked as visited, the shortest path from the initial node to the destination node can be reconstructed by backtracking from the destination to the initial node, following the path of smallest tentative distances.
Dijkstra's algorithm guarantees the shortest path if all edge weights are non-negative. However, it may not work correctly if there are negative edge weights. For graphs with negative weights, algorithms like the Bellman-Ford algorithm are more appropriate.
Dijkstra's algorithm has a time complexity of O(V^2) for an adjacency matrix representation and O((V + E) * log(V)) using a priority queue with an adjacency list representation, where V is the number of vertices and E is the number of edges.
Code Examples
#1 Dijkstra's implement in Python
Code -
Python Programming
import heapq
def dijkstra(graph, start):
# Initialize distances with infinity for all nodes except the start node
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# Use a priority queue to keep track of the nodes with the smallest tentative distance
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# Skip if the current distance is greater than the known distance
if current_distance > distances[current_node]:
continue
# Update distances for neighboring nodes
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# If a shorter path is found, update the distance and add to the priority queue
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}
}
start_node = 'A'
result = dijkstra(graph, start_node)
print(f"Shortest distances from node {start_node}: {result}")
#2 Dijkstra's implement in Java
Code -
Java Programming
import java.util.*;
class Graph {
private int V;
private List < List(V);
for (int i = 0; i < V; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination, int weight) {
Node node = new Node(destination, weight);
adjList.get(source).add(node);
}
public void dijkstra(int startVertex) {
PriorityQueue < Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));
int[] distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
priorityQueue.add(new Node(startVertex, 0));
distance[startVertex] = 0;
while (!priorityQueue.isEmpty()) {
int currentVertex = priorityQueue.poll().vertex;
for (Node neighbor : adjList.get(currentVertex)) {
int newDistance = distance[currentVertex] + neighbor.weight;
if (newDistance < distance[neighbor.vertex]) {
distance[neighbor.vertex] = newDistance;
priorityQueue.add(new Node(neighbor.vertex, newDistance));
}
}
}
// Print the shortest distances
System.out.println("Shortest distances from vertex " + startVertex + ":");
for (int i = 0; i < V; i++) {
System.out.println("To vertex " + i + ": " + distance[i]);
}
}
private static class Node {
int vertex;
int weight;
public Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
}
public class DijkstraExample {
public static void main(String[] args) {
int V = 5;
Graph graph = new Graph(V);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 3, 1);
graph.addEdge(1, 2, 3);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 2, 5);
graph.addEdge(3, 4, 4);
int startVertex = 0;
graph.dijkstra(startVertex);
}
}
#3 Dijkstra's implement in C
Code -
C Programming
#include <stdio.h>
#include <limits.h>
#define V 9 // Number of vertices in the graph
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array dist[i] holds the shortest distance from src to i
int sptSet[V]; // sptSet[i] will be true if vertex i is included in the shortest path tree or the shortest distance from src to i is finalized
// Initialize all distances as INFINITE and sptSet[] as false
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = 1;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++) {
// Update dist[v] only if it is not in the sptSet, there is an edge from u to v, and the total weight of path from src to v through u is less than the current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the constructed distance array
printSolution(dist);
}
int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}};
dijkstra(graph, 0);
return 0;
}
#4 Dijkstra's implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Define a structure to represent a graph edge
struct Edge {
int destination;
int weight;
};
// Define a structure to represent a graph node
struct Node {
vector < Edge> edges;
};
// Dijkstra's algorithm function
void dijkstra(vector < Node>& graph, int start) {
int n = graph.size();
vector<int> distance(n, INT_MAX);
vector < bool> visited(n, false);
// Priority queue to get the minimum distance vertex efficiently
priority_queue<pair<int, int>, vector<pair<int, int>>, greater < pair<int, int>>> pq;
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
// Update the distance to adjacent nodes
for (const Edge& edge : graph[u].edges) {
int v = edge.destination;
int w = edge.weight;
if (!visited[v] && distance[u] != INT_MAX && distance[u] + w < distance[v]) {
distance[v] = distance[u] + w;
pq.push({distance[v], v});
}
}
}
// Output the shortest distances from the start node
cout << "Shortest distances from node " << start << ":\n";
for (int i = 0; i < n; ++i) {
cout << "Node " << i << ": " << distance[i] << endl;
}
}
int main() {
// Example graph representation
vector < Node> graph = {
{{1, 4}, {2, 1}},
{{3, 2}},
{{1, 2}, {3, 5}},
{}
};
// Start Dijkstra's algorithm from node 0
dijkstra(graph, 0);
return 0;
}
Demonstration
Dijkstra's Data Structure and Algorithm