Purpose
- Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
- Commonly used in GPS navigation, network routing, and logistics planning.
Key Concepts
- Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
- Source Vertex: The starting point for finding shortest paths.
- Shortest Path: The path with the minimum total weight between two vertices.
Algorithm Steps
Initialization:
- Create a set
Sto store visited vertices (initially empty). - Initialize an array
distanceswith infinite values for all vertices except the source, which is set to 0. - Create a priority queue
Qto store vertices, prioritized by their tentative distances. - Add the source vertex to
Q.
- Create a set
Exploration Loop:
- While
Qis not empty:- Extract the vertex
uwith the minimum distance fromQ. - Add
uto the setS(mark as visited). - For each neighbor vertex
vofu:- If
vis not visited and the distance tovthroughuis shorter than its current distance:- Update the distance to
vin thedistancesarray. - Add
vto the priority queueQ(or update its priority if already present).
- Update the distance to
- If
- Extract the vertex
- While
Result:
- The
distancesarray now contains the shortest distances from the source vertex to all other vertices. - To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.
- The
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;
public class Dijkstra {
public static List dijkstra(Graph graph, int source) {
int[] distances = new int[graph.numVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
pq.offer(source);
boolean[] visited = new boolean[graph.numVertices];
while (!pq.isEmpty()) {
int u = pq.poll();
visited[u] = true;
for (Edge edge : graph.adjacencyList.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.offer(v);
}
}
}
return Arrays.stream(distances).boxed().collect(Collectors.toList());
}
public static Graph createRandomGraph(int numVertices) {
Graph graph = new Graph(numVertices);
Random random = new Random();
// Add edges with random weights
for (int i = 0; i < 9; i++) {
for (int j = i + 1; j < 9; j++) {
// Decide whether to create an edge with 50% probability
if (random.nextBoolean()) {
int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
graph.addEdge(i, j, weight);
graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
}
}
}
return graph;
}
public static void main(String[] args) {
// Create a sample graph
Graph graph = createRandomGraph(9);
graph.visualize();
int source = 0;
List distances = dijkstra(graph, source);
System.out.println("Shortest distances from " + source + ": " + distances);
}
public static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static class Graph {
int numVertices;
List> adjacencyList;
Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
}
void addEdge(int from, int to, int weight) {
adjacencyList.get(from).add(new Edge(to, weight));
}
void visualize() {
System.out.println("Graph Visualization:\n");
for (int vertex = 0; vertex < numVertices; vertex++) {
System.out.print(vertex + " -> ");
for (Edge edge : adjacencyList.get(vertex)) {
System.out.print(edge.to + "(" + edge.weight + ") ");
}
System.out.println();
}
}
}
}
Explanation of code
Graph Representation
- The
Graphclass models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights. - The
Edgeclass encapsulates the destination vertex and weight of an edge.
- The
Dijkstra's Algorithm Implementation
- The
dijkstra(Graph, source)method implements the algorithm's logic:- It maintains a priority queue to explore vertices in order of their tentative distances.
- It iteratively relaxes edges to update distances and explore reachable vertices.
- It ultimately returns a list of the shortest distances from the source vertex to all other vertices.
- The
Random Graph Generation
- The
createRandomGraph(numVertices)method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.
- The
