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.
1#include <vector>
2#include <queue>
3#include <unordered_map>
4#include <limits.h>
5using namespace std;
6
7int networkDelayTime(vector<vector<int>>& times, int n, int k) {
8 unordered_map<int, vector<pair<int, int>>> graph;
9 for (auto& time : times) {
10 graph[time[0]].emplace_back(time[1], time[2]);
11 }
12 vector<int> dist(n + 1, INT_MAX);
13 dist[k] = 0;
14 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
15 pq.emplace(0, k);
16 while (!pq.empty()) {
17 auto [time, node] = pq.top();
18 pq.pop();
19 if (time > dist[node]) continue;
20 for (auto& [neigh, weight] : graph[node]) {
21 if (dist[node] + weight < dist[neigh]) {
22 dist[neigh] = dist[node] + weight;
23 pq.emplace(dist[neigh], neigh);
24 }
25 }
26 }
27 int maxTime = 0;
28 for (int i = 1; i <= n; ++i) {
29 if (dist[i] == INT_MAX) return -1;
30 maxTime = max(maxTime, dist[i]);
31 }
32 return maxTime;
33}This C++ solution also uses a priority queue to process nodes with the smallest accumulated distance first, thereby ensuring we compute the shortest distance to each node from the starting node. The edge list is initially transformed into an adjacency list represented by an unordered_map.
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.