#include #include #include #include #include #include #include struct Edge { int from; int to; int cost; }; int main() { std::vector names = {"A", "B", "C", "D"}; std::vector edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}}; int n = static_cast(names.size()); std::vector>> adj(n); for (const Edge& e : edges) { adj[e.from].push_back({e.to, e.cost}); adj[e.to].push_back({e.from, e.cost}); } const int INF = std::numeric_limits::max(); std::vector dist(n, INF); std::vector prev(n, -1); dist[0] = 0; using Item = std::pair; // (distance, node) std::priority_queue, std::greater> pq; pq.push({0, 0}); while (!pq.empty()) { Item top = pq.top(); pq.pop(); int d = top.first; int u = top.second; if (d > dist[u]) continue; for (const auto& edge : adj[u]) { int v = edge.first; int w = edge.second; if (d + w < dist[v]) { dist[v] = d + w; prev[v] = u; pq.push({dist[v], v}); } } } for (int v = 0; v < n; v++) { if (v == 0) { std::cout << names[v] << " dist 0 (this router)\n"; continue; } int hop = v; while (prev[hop] != 0) hop = prev[hop]; std::cout << names[v] << " dist " << dist[v] << " first hop " << names[hop] << "\n"; } return 0; }

Routing and sockets

This lesson is part of Practice and above