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.
1using System;
2using System.Collections.Generic;
3
4public class Graph {
5 private int n;
6 private List<List<(int, int)>> adj;
7
8 public Graph(int n, int[][] edges) {
9 this.n = n;
10 this.adj = new List<List<(int, int)>>();
11 for (int i = 0; i < n; i++) {
12 adj.Add(new List<(int, int)>());
13 }
14 foreach (var edge in edges) {
15 adj[edge[0]].Add((edge[1], edge[2]));
16 }
17 }
18
19 public void AddEdge(int[] edge) {
20 adj[edge[0]].Add((edge[1], edge[2]));
21 }
22
23 public int ShortestPath(int node1, int node2) {
24 int[] dist = new int[n];
25 Array.Fill(dist, int.MaxValue);
26 dist[node1] = 0;
27
28 var pq = new SortedSet<(int Distance, int Vertex)>(Comparer<(int, int)>.Create((x, y) => {
29 int result = x.Distance.CompareTo(y.Distance);
30 return result == 0 ? x.Vertex.CompareTo(y.Vertex) : result;
31 }));
32 pq.Add((0, node1));
33
34 while (pq.Count > 0) {
35 var current = pq.Min;
36 pq.Remove(current);
37 int u = current.Vertex;
38 int curDist = current.Distance;
39
40 if (u == node2) return curDist;
41 if (curDist > dist[u]) continue;
42
43 foreach (var (v, cost) in adj[u]) {
44 if (dist[u] + cost < dist[v]) {
45 dist[v] = dist[u] + cost;
46 pq.Add((dist[v], v));
47 }
48 }
49 }
50 return -1;
51 }
52
53 public static void Main() {
54 int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
55 Graph g = new Graph(4, edges);
56 Console.WriteLine(g.ShortestPath(3, 2)); // Output: 6
57 Console.WriteLine(g.ShortestPath(0, 3)); // Output: -1
58 g.AddEdge(new int[] { 1, 3, 4 });
59 Console.WriteLine(g.ShortestPath(0, 3)); // Output: 6
60 }
61}The C# implementation leverages a `SortedSet` for prioritizing graph nodes based on their cumulative path distance, thereby optimizing time complexity when executing Dijkstra's shortest path algorithm.
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.
1class Graph:
2 def __init__(self, n, edges):
3 self.n = n
4 self.dist = [[float('inf')] * n for _ in range(n)]
5 for i in range(n):
6 self.dist[i][i] = 0
7 for u, v, cost in edges:
8 self.dist[u][v] = cost
9 self.floyd_warshall()
10
11 def floyd_warshall(self):
12 for k in range(self.n):
13 for i in range(self.n):
14 for j in range(self.n):
15 if self.dist[i][k] != float('inf') and self.dist[k][j] != float('inf'):
16 self.dist[i][j] = min(self.dist[i][j], self.dist[i][k] + self.dist[k][j])
17
18 def addEdge(self, edge):
19 u, v, cost = edge
20 self.dist[u][v] = cost
21 self.floyd_warshall()
22
23 def shortestPath(self, node1, node2):
24 return -1 if self.dist[node1][node2] == float('inf') else self.dist[node1][node2]
25
26# Demonstration
27if __name__ == "__main__":
28 edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
29 graph = Graph(4, edges)
30 print(graph.shortestPath(3, 2)) # Output: 6
31 print(graph.shortestPath(0, 3)) # Output: -1
32 graph.addEdge([1, 3, 4])
33 print(graph.shortestPath(0, 3)) # Output: 6
34Python computes all pairs’ shortest paths upfront, storing these for efficient query handling, factoring additional edges via necessary resultant matrix updates.