Sponsored
Sponsored
Dijkstra's Algorithm is effective for finding the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. By implementing a priority queue, we repeatedly select the node with the smallest tentative distance, update its neighboring nodes, and do this until all nodes have been processed.
Time Complexity: O((N + E) log N), where E is the number of edges.
Space Complexity: O(N + E) for constructing the adjacency list.
1import heapq
2
3def networkDelayTime(times, n, k):
4 graph = {i: {} for i in range(1, n + 1)}
5 for u, v, w in times:
6 graph[u][v] = w
7
8 pq = [(0, k)]
9 dist = {}
10 while pq:
11 time, node = heapq.heappop(pq)
12 if node in dist:
13 continue
14 dist[node] = time
15 for neighbor in graph[node]:
16 if neighbor not in dist:
17 heapq.heappush(pq, (time + graph[node][neighbor], neighbor))
18
19 return max(dist.values()) if len(dist) == n else -1
20The Python solution uses a priority queue (min-heap) to always expand the least cost node using the heapq module. It keeps track of each node’s shortest distance from the starting node. If not all nodes are reached, we return -1.
The Bellman-Ford Algorithm is efficient in handling negative edge weights, which doesn't apply here but showcases versatility in cyclical graphs. It operates by executing N-1 passes over each edge and updating the shortest paths stored for each node.
Time Complexity: O(N * E).
Space Complexity: O(N).
1import java.util.Arrays;
2import java
This Java approach utilizes the Bellman-Ford algorithm. The array holds the shortest path estimate where each pass attempts to update the shortest path based on the available edges. It completes in N-1 passes.