Introduction
Dijkstra’s Algorithm is a fundamental algorithm in graph theory used to find the shortest path from a single node to all other nodes in a weighted graph. It is commonly used in network routing protocols and geographical mapping systems. The algorithm assumes that all edge weights are non-negative.
How Dijkstra’s Algorithm Works
The algorithm maintains a set of visited nodes and calculates tentative distances from the source node to every other node in the graph. At each step, it selects the unvisited node with the smallest estimated distance, updates the distances of its neighbors, and marks it as visited. This process continues until all nodes have been visited or the destination node has been reached.
Key Concepts
- Priority Queue: A priority queue (often implemented as a min-heap) is used to efficiently select the node with the smallest estimated distance.
- Distance Array: Stores the current known shortest distance from the source to each node.
- Visited Set: Keeps track of nodes whose shortest distances from the source have been finalized.
Java Implementation Example
The following Java code demonstrates how to implement Dijkstra’s Algorithm using an adjacency list and a priority queue.
class DijkstraAlg {
static class GraphEdge {
int target, weight;
GraphEdge(int target, int weight) {
this.target = target;
this.weight = weight;
}
}
static class GraphNode implements Comparable<GraphNode> {
int vertex, distance;
GraphNode(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
public int compareTo(GraphNode other) {
return Integer.compare(this.distance, other.distance);
}
}
public static int[] dijkstra(List<List<GraphEdge>> graph, int source) {
int graphSize = graph.size();
int[] dist = new int[graphSize];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<GraphNode> priorQ = new PriorityQueue<>();
priorQ.add(new GraphNode(source, 0));
while (!priorQ.isEmpty()) {
GraphNode current = priorQ.poll();
int vert = current.vertex;
for (GraphEdge edge : graph.get(vert)) {
int v = edge.target;
int weight = edge.weight;
if (dist[vert] + weight < dist[v]) {
dist[v] = dist[vert] + weight;
priorQ.add(new GraphNode(v, dist[v]));
}
}
}
return dist;
}
public static void main(String[] args) {
int numVertices = 5;
List<List<GraphEdge>> g = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
g.add(new ArrayList<>());
}
g.get(0).add(new GraphEdge(1, 10));
g.get(0).add(new GraphEdge(4, 5));
g.get(1).add(new GraphEdge(2, 1));
g.get(1).add(new GraphEdge(4, 2));
g.get(2).add(new GraphEdge(3, 4));
g.get(3).add(new GraphEdge(2, 6));
g.get(3).add(new GraphEdge(0, 7));
g.get(4).add(new GraphEdge(1, 3));
g.get(4).add(new GraphEdge(2, 9));
g.get(4).add(new GraphEdge(3, 2));
int[] distances = dijkstra(g, 0);
System.out.println("Shortest distances from node 0:");
for (int i = 0; i < distances.length; i++) {
System.out.println("To node " + i + " : " + distances[i]);
}
}
}
Example Output
Assuming the graph is set up as shown in the code, the output would be:
vbnetCopiaModificaShortest distances from node 0:
To node 0 : 0
To node 1 : 8
To node 2 : 9
To node 3 : 7
To node 4 : 5
Time Complexity
Dijkstra’s Algorithm has a time complexity that varies based on the data structures implemented. With a binary heap-based priority queue, its time complexity is O((V + E) log V), where V represents the number of vertices and E the number of edges.
Conclusion
Dijkstra’s Algorithm is a powerful and efficient method for computing the shortest paths in a graph with non-negative edge weights. It’s a foundational algorithm for understanding graph traversal and pathfinding in computer science.
You can find the example code on Github.