単一始点最短路(Dijkstra)
目的
負辺のないグラフで単一始点全点間最短路を求めるアルゴリズム. 各地点でもっとも近い頂点から距離が確定していく. 距離順でソートされたヒープを用いると, 効率よく距離を確定していくことができる.
オーダー
O(ElogV)
条件
dijkstra(g, s): 重み付きグラフ g で, 頂点 s から全点間の最短コストを求める. dist には最短コスト(到達できないとき型の最大値), from にはその頂点の直前に訪れた頂点(頂点 s または到達できない頂点は−1), id はその頂点の直前に使った辺番号が格納される.
コード
template <typename T> struct ShortestPath { vector<T> dist; vector<int> from, id; }; template <typename T> ShortestPath<T> dijkstra(const Graph<T> &g, int s) { const auto INF = numeric_limits<T>::max(); vector<T> dist(g.size(), INF); vector<int> from(g.size(), -1), id(g.size(), -1); using Pi = pair<T, int>; priority_queue<Pi, vector<Pi>, greater<>> que; dist[s] = 0; que.emplace(dist[s], s); while (!que.empty()) { T cost; int idx; tie(cost, idx) = que.top(); que.pop(); if (dist[idx] < cost) continue; for (auto &e : g.g[idx]) { auto next_cost = cost + e.cost; if (dist[e.to] <= next_cost) continue; dist[e.to] = next_cost; from[e.to] = idx; id[e.to] = e.idx; que.emplace(dist[e.to], e.to); } } return {dist, from, id}; }
コードテスト
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define REP(i, x) for (ll i = 0; i < (ll)(x); i++) template <typename T = int> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template <typename T = int> struct Graph { vector<vector<Edge<T>>> g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) //Mは読み込み数、paddingは0-index調整、weighted true で重みあり、directed true で有向 { for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if (weighted) cin >> c; if (directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } }; template <typename T = int> using Edges = vector<Edge<T>>; template <typename T> struct ShortestPath { vector<T> dist; vector<int> from, id; }; template <typename T> ShortestPath<T> dijkstra(const Graph<T> &g, int s) { const auto INF = numeric_limits<T>::max(); vector<T> dist(g.size(), INF); vector<int> from(g.size(), -1), id(g.size(), -1); using Pi = pair<T, int>; priority_queue<Pi, vector<Pi>, greater<>> que; dist[s] = 0; que.emplace(dist[s], s); while (!que.empty()) { T cost; int idx; tie(cost, idx) = que.top(); que.pop(); if (dist[idx] < cost) continue; for (auto &e : g.g[idx]) { auto next_cost = cost + e.cost; if (dist[e.to] <= next_cost) continue; dist[e.to] = next_cost; from[e.to] = idx; id[e.to] = e.idx; que.emplace(dist[e.to], e.to); } } return {dist, from, id}; } int main() { ll N, M, S, T; cin >> N >> M >> S >> T; Graph<ll> g(N); g.read(M, 0, true, true); auto ret = dijkstra(g, S); if (ret.from[T] == -1) { cout << -1 << endl; } else { cout << ret.dist[T] << " "; vector<pair<int, int>> es; while (S != T) { es.emplace_back(ret.from[T], T); T = ret.from[T]; } reverse(begin(es), end(es)); cout << es.size() << "\n"; for (auto &p : es) cout << p.first << " " << p.second << "\n"; } }