Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative weights. We can adapt it to efficiently find the shortest path for this problem.
Time Complexity: O(V^2), where V is the number of vertices since we're using an adjacency matrix and no priority queue to obtain the minimum distance vertex.
Space Complexity: O(V^2) due to the adjacency matrix storage requirements.
1import java.util.*;
2
3class Graph {
4 private int n;
5 private List<List<int[]>> adj;
6
7 public Graph(int n, int[][] edges) {
8 this.n = n;
9 this.adj = new ArrayList<>();
10 for (int i = 0; i < n; i++) {
11 adj.add(new ArrayList<>());
12 }
13 for (int[] edge : edges) {
14 adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
15 }
16 }
17
18 public void addEdge(int[] edge) {
19 adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
20 }
21
22 public int shortestPath(int node1, int node2) {
23 int[] dist = new int[n];
24 Arrays.fill(dist, Integer.MAX_VALUE);
25 dist[node1] = 0;
26 PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
27 pq.offer(new int[]{node1, 0});
28
29 while (!pq.isEmpty()) {
30 int[] current = pq.poll();
31 int u = current[0];
32 int curDist = current[1];
33
34 if (u == node2) return curDist;
35 if (curDist > dist[u]) continue;
36
37 for (int[] neighbor : adj.get(u)) {
38 int v = neighbor[0];
39 int weight = neighbor[1];
40 if (dist[u] + weight < dist[v]) {
41 dist[v] = dist[u] + weight;
42 pq.offer(new int[]{v, dist[v]});
43 }
44 }
45 }
46 return -1;
47 }
48
49 public static void main(String[] args) {
50 int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
51 Graph graph = new Graph(4, edges);
52 System.out.println(graph.shortestPath(3, 2)); // Output: 6
53 System.out.println(graph.shortestPath(0, 3)); // Output: -1
54 graph.addEdge(new int[]{1, 3, 4});
55 System.out.println(graph.shortestPath(0, 3)); // Output: 6
56 }
57}Java solution uses a priority queue implemented by `PriorityQueue` class for Dijkstra's algorithm to ensure O(log V) minimum distance updates.
The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find shortest paths between all pairs of vertices in a weighted graph. This approach is more suited when there are frequent shortest path queries between multiple different node pairs.
Time Complexity: O(n^3), where n is the number of vertices, arising from the three nested loops.
Space Complexity: O(n^2) due to the distance matrix storage covering all node pairs.
1import java.util.*;
2
3class Graph {
4 private int n;
5 private int[][] dist;
6
7 public Graph(int n, int[][] edges) {
8 this.n = n;
9 dist = new int[n][n];
10 for (int[] row : dist)
11 Arrays.fill(row, Integer.MAX_VALUE);
12 for (int i = 0; i < n; i++)
13 dist[i][i] = 0;
14 for (int[] edge : edges) {
15 dist[edge[0]][edge[1]] = edge[2];
16 }
17 floydWarshall();
18 }
19
20 public void floydWarshall() {
21 for (int k = 0; k < n; k++) {
22 for (int i = 0; i < n; i++) {
23 for (int j = 0; j < n; j++) {
24 if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE)
25 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
26 }
27 }
28 }
29 }
30
31 public void addEdge(int[] edge) {
32 dist[edge[0]][edge[1]] = edge[2];
33 floydWarshall();
34 }
35
36 public int shortestPath(int node1, int node2) {
37 return dist[node1][node2] == Integer.MAX_VALUE ? -1 : dist[node1][node2];
38 }
39
40 public static void main(String[] args) {
41 int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
42 Graph graph = new Graph(4, edges);
43 System.out.println(graph.shortestPath(3, 2)); // Output: 6
44 System.out.println(graph.shortestPath(0, 3)); // Output: -1
45 graph.addEdge(new int[]{1, 3, 4});
46 System.out.println(graph.shortestPath(0, 3)); // Output: 6
47 }
48}Java implements Floyd-Warshall to precompute path efficiencies across the graph's entirety, recalculating these values upon any edge addition to account for potential novel shortest routes.