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.
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.