Dijkstra's algorithm is a well-known algorithm used to find the shortest path between two vertices in a weighted graph. It guarantees the shortest path from a source vertex to all other vertices. This algorithm is widely used in various applications, such as GPS navigation systems, network routing protocols, and airline travel planning.
The basic idea behind Dijkstra's algorithm is to continuously update the shortest path distances from the source vertex to all other vertices in the graph. It maintains a priority queue of vertices to explore, sorted by their current shortest distance from the source. At each step, it selects the vertex with the smallest current distance and relaxes the edges connected to it.
Let's take a look at an implementation of Dijkstra's algorithm in Java:
1class Graph {
2 private int V;
3 private int[][] graph;
4
5 public Graph(int V) {
6 this.V = V;
7 graph = new int[V][V];
8 }
9
10 public void addEdge(int src, int dest, int weight) {
11 graph[src][dest] = weight;
12 }
13
14 public void dijkstra(int source) {
15 // Initialize distance array
16 int[] dist = new int[V];
17 Arrays.fill(dist, Integer.MAX_VALUE);
18 dist[source] = 0;
19
20 // Initialize visited array
21 boolean[] visited = new boolean[V];
22
23 // Initialize priority queue
24 PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
25 pq.offer(source);
26
27 while (!pq.isEmpty()) {
28 int vertex = pq.poll();
29 visited[vertex] = true;
30
31 // Relax edges connected to the current vertex
32 for (int neighbor = 0; neighbor < V; neighbor++) {
33 int weight = graph[vertex][neighbor];
34
35 if (weight > 0 && !visited[neighbor]) {
36 int newDistance = dist[vertex] + weight;
37
38 if (newDistance < dist[neighbor]) {
39 // Update shortest distance to neighbor
40 dist[neighbor] = newDistance;
41
42 // Add neighbor to priority queue
43 pq.offer(neighbor);
44 }
45 }
46 }
47 }
48
49 // Print the shortest distances from the source vertex
50 System.out.println(Arrays.toString(dist));
51 }
52
53 public static void main(String[] args) {
54 int V = 5; // Number of vertices
55 Graph graph = new Graph(V);
56
57 // Add edges
58 graph.addEdge(0, 1, 4);
59 graph.addEdge(0, 2, 1);
60 graph.addEdge(1, 3, 1);
61 graph.addEdge(2, 1, 2);
62 graph.addEdge(2, 3, 5);
63 graph.addEdge(3, 4, 3);
64
65 graph.dijkstra(0);
66 }
67}xxxxxxxxxx}import java.util.Arrays;import java.util.PriorityQueue;class Graph { private int V; private int[][] graph; public Graph(int V) { this.V = V; graph = new int[V][V]; } public void addEdge(int src, int dest, int weight) { graph[src][dest] = weight; } public void dijkstra(int source) { int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); boolean[] visited = new boolean[V]; dist[source] = 0; PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]); pq.offer(source); while (!pq.isEmpty()) { int vertex = pq.poll();