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 heapq
2
3class Graph:
4 def __init__(self, n, edges):
5 self.n = n
6 self.adj = [[] for _ in range(n)]
7 for u, v, cost in edges:
8 self.adj[u].append((v, cost))
9
10 def addEdge(self, edge):
11 u, v, cost = edge
12 self.adj[u].append((v, cost))
13
14 def shortestPath(self, node1, node2):
15 dist = [float('inf')] * self.n
16 dist[node1] = 0
17 pq = [(0, node1)]
18
19 while pq:
20 curDist, u = heapq.heappop(pq)
21 if u == node2:
22 return curDist
23 if curDist > dist[u]:
24 continue
25 for v, cost in self.adj[u]:
26 if dist[u] + cost < dist[v]:
27 dist[v] = dist[u] + cost
28 heapq.heappush(pq, (dist[v], v))
29 return -1
30
31# Demonstration
32if __name__ == "__main__":
33 edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]
34 graph = Graph(4, edges)
35 print(graph.shortestPath(3, 2)) # Output: 6
36 print(graph.shortestPath(0, 3)) # Output: -1
37 graph.addEdge([1, 3, 4])
38 print(graph.shortestPath(0, 3)) # Output: 6
39Python implementation utilizes `heapq` for the priority queue, allowing Dijkstra's approach to effectively evaluate the shortest path by updating minimum costs as graph exploration progresses.
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 constructor(n, edges) {
3 this.n = n;
4 this.dist = Array.from({ length: n }, () => Array(n).fill(Infinity));
5 for (let i = 0; i < n; i++) {
6 this.dist[i][i] = 0;
7 }
8 for (const [u, v, cost] of edges) {
9 this.dist[u][v] = cost;
10 }
11 this.floydWarshall();
12 }
13
14 floydWarshall() {
15 const { n, dist } = this;
16 for (let k = 0; k < n; k++) {
17 for (let i = 0; i < n; i++) {
18 for (let j = 0; j < n; j++) {
19 if (dist[i][k] < Infinity && dist[k][j] < Infinity) {
20 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
21 }
22 }
23 }
24 }
25 }
26
27 addEdge(edge) {
28 const [u, v, cost] = edge;
29 this.dist[u][v] = cost;
30 this.floydWarshall();
31 }
32
33 shortestPath(node1, node2) {
34 return this.dist[node1][node2] === Infinity ? -1 : this.dist[node1][node2];
35 }
36}
37
38// Demonstration
39const edges = [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]];
40const graph = new Graph(4, edges);
41console.log(graph.shortestPath(3, 2)); // Output: 6
42console.log(graph.shortestPath(0, 3)); // Output: -1
43graph.addEdge([1, 3, 4]);
44console.log(graph.shortestPath(0, 3)); // Output: 6
45JavaScript version calculates all shortest paths by initializing them through the core Floyd-Warshall procedure and updates upon edge modifications to maintain consistent optimality in path results.