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.
1class Graph {
2 constructor(n, edges) {
3 this.n = n;
4 this.adj = Array.from({ length: n }, () => []);
5 for (const [u, v, cost] of edges) {
6 this.adj[u].push([v, cost]);
7 }
8 }
9
10 addEdge(edge) {
11 const [u, v, cost] = edge;
12 this.adj[u].push([v, cost]);
13 }
14
15 shortestPath(node1, node2) {
16 const dist = new Array(this.n).fill(Infinity);
17 dist[node1] = 0;
18 const pq = new PriorityQueue((a, b) => a[0] < b[0]);
19 pq.enqueue([0, node1]);
20
21 while (!pq.isEmpty()) {
22 const [curDist, u] = pq.dequeue();
23 if (u === node2) return curDist;
24 if (curDist > dist[u]) continue;
25
26 for (const [v, cost] of this.adj[u]) {
27 if (dist[u] + cost < dist[v]) {
28 dist[v] = dist[u] + cost;
29 pq.enqueue([dist[v], v]);
30 }
31 }
32 }
33 return -1;
34 }
35}
36
37class PriorityQueue {
38 constructor(comparator) {
39 this.data = [];
40 this.comparator = comparator;
41 }
42
43 enqueue(value) {
44 this.data.push(value);
45 this.data.sort(this.comparator);
46 }
47
48 dequeue() {
49 return this.data.shift();
50 }
51
52 isEmpty() {
53 return this.data.length === 0;
54 }
55}
56
57// Demonstration
58const edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]];
59const graph = new Graph(4, edges);
60console.log(graph.shortestPath(3, 2)); // Output: 6
61console.log(graph.shortestPath(0, 3)); // Output: -1
62graph.addEdge([1, 3, 4]);
63console.log(graph.shortestPath(0, 3)); // Output: 6
64JavaScript utilizes a simple priority queue implementation to keep track of and process nodes by minimized distances while computing shortest paths.
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.
1using System;
2
3public class 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 i = 0; i < n; i++)
11 for (int j = 0; j < n; j++)
12 dist[i, j] = (i == j) ? 0 : int.MaxValue;
13 foreach (var edge in edges)
14 dist[edge[0], edge[1]] = edge[2];
15 FloydWarshall();
16 }
17
18 private void FloydWarshall() {
19 for (int k = 0; k < n; k++) {
20 for (int i = 0; i < n; i++) {
21 for (int j = 0; j < n; j++) {
22 if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue)
23 dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
24 }
25 }
26 }
27 }
28
29 public void AddEdge(int[] edge) {
30 dist[edge[0], edge[1]] = edge[2];
31 FloydWarshall();
32 }
33
34 public int ShortestPath(int node1, int node2) {
35 return dist[node1, node2] == int.MaxValue ? -1 : dist[node1, node2];
36 }
37
38 public static void Main(String[] args) {
39 int[][] edges = new int[][] { new int[] { 0, 2, 5 }, new int[] { 0, 1, 2 }, new int[] { 1, 2, 1 }, new int[] { 3, 0, 3 } };
40 Graph graph = new Graph(4, edges);
41 Console.WriteLine(graph.ShortestPath(3, 2)); // Output: 6
42 Console.WriteLine(graph.ShortestPath(0, 3)); // Output: -1
43 graph.AddEdge(new int[] { 1, 3, 4 });
44 Console.WriteLine(graph.ShortestPath(0, 3)); // Output: 6
45 }
46}Floyd-Warshall precomputes full path pair information upfront for C#, with each edge insertion prompting algorithm re-execution, ensuring all shortest distances remain current.