Problem 38: Dijkstra's Shortest Path
Problem Statement: Given a weighted directed graph with n nodes and m edges, and a source node 1, compute the shortest distance from node 1 to every other node. If a node is unreachable, print -1 for that node.
Input
The first line contains two integers n and m. Each of the next m lines contains three integers u, v, and w representing an edge from u to v with weight w.
Output
Print n space-separated integers representing the shortest distances from node 1 to each node (1-indexed).
Examples
Input:
5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
Output:
0 2 3 9 6
Solution Explanation
Method 1: Use Dijkstra's algorithm with a priority queue to efficiently compute the shortest path distances from the source to all nodes. Method 2: For smaller graphs, you could use a simple O(n^2) approach by repeatedly selecting the unvisited node with the smallest distance, but Dijkstra's algorithm with a min-heap is preferred for efficiency.
Solution in C++
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector>> adj(n+1);
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
}
vector dist(n+1, INF);
dist[1] = 0;
priority_queue, vector>, greater>>pq;
pq.push({0, 1});
while(!pq.empty()){
auto [d, u] = pq.top(); pq.pop();
if(d != dist[u]) continue;
for(auto &edge: adj[u]){
int v = edge.first;
int w = edge.second;
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for(int i = 1; i <= n; i++){
cout << (dist[i] == INF ? -1 : dist[i]) << " ";
}
cout << "
";
return 0;
}