Shortest Path with Weights
GOALFind the cheapest route when edges cost different amounts.
This one is hard — read it after you are comfortable with BFS and the priority queue. When roads have different lengths, fewest-roads no longer means shortest. Dijkstra's algorithm repeatedly takes the nearest unfinished node and improves the routes through it.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n = 4;
vector<vector<pair<int,int>>> adj(n);
// adj[from] = list of (to, cost)
adj[0].push_back({1, 1});
adj[0].push_back({2, 8});
adj[1].push_back({2, 2});
adj[2].push_back({3, 3});
vector<int> dist(n, 1000000000);
dist[0] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
pair<int,int> top = pq.top();
pq.pop();
int d = top.first, v = top.second;
if (d > dist[v]) continue;
for (pair<int,int> e : adj[v]) {
int to = e.first, cost = e.second;
if (dist[v] + cost < dist[to]) {
dist[to] = dist[v] + cost;
pq.push({dist[to], to});
}
}
}
cout << dist[3] << endl;
return 0;
}6
//LINE BY LINE
Watch it run
Four nodes, weighted edges. Every distance but the start is unknown.
Choosing between them
All three answer "find a route", but under different conditions. Choose wrong and nothing errors — the answer is simply wrong.
| Situation | Algorithm |
|---|---|
| Зөвхөн холбогдсон эсэх / Only need connectivity | DFS |
| Бүх алхам ижил зардалтай / Every step costs the same | BFS |
| Холбоос өөр өөр жинтэй / Edges have different weights | Дейкстра / Dijkstra |
| Сөрөг жинтэй холбоос / Some weights are negative | Дейкстра БОЛОХГҮЙ / NOT Dijkstra |
With every weight equal to 1, Dijkstra gives exactly the same answer as BFS, only slower. So when BFS is enough, use BFS.
The stale entries
Dijkstra can push the same node several times, once for each shorter route it finds. When you pop, you have to notice the out-of-date ones and skip them.
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // a shorter route already went throughLeave that line out and the answer is still right, but each node is processed many times over and a large graph times out.