013 - Passing(★5) Editorial by kichi2004_
この解説では,以下の 3 ステップに分けて紹介します。
1. グラフの最短経路問題について
2. この問題に最短経路問題をどのように適用するか
3. 解法(サンプルコード:C++, Python)
1. グラフの最短経路問題について
頂点数 \(V\) 辺数 \(E\) の重みつきグラフについて,ある頂点からすべての頂点までの最短路長(最短経路の長さ)を求めるアルゴリズムは,以下のようなものがあります。
Dijkstra(ダイクストラ)法
コストが負の辺が存在しない場合に適用できます。
計算量は \(O((E+V) \log V)\) です。(さらに高速化して \(O(E + V \log V)\) とする方法も存在します。)
詳細については Wikipedia の記事 をご覧ください。
Bellman-Ford(ベルマン-フォード)法
Bellman-Ford 法は,辺のコストが負の場合でも適用できます。また,負閉路が存在する場合でも,それを検出することができます。 計算量は \(O(VE)\) です。
詳細については Wikipedia の記事 をご覧ください。
2. この問題に最短経路問題をどのように適用するか
この問題では,頂点 \(1\) から頂点 \(k\) を経由して,頂点 \(N\) まで至る最短路長を求める必要があります。
各頂点それぞれからすべての頂点への最短路長を求めて,頂点 \(i\) から頂点 \(j\) までの最短路長を \(d_{i,j}\) と表すことにします。この値は,各頂点からダイクストラ法やワーシャルフロイド法を使って求めることができます。
この値を利用すると,頂点 \(k\) に対する答えは \(d_{1,k} + d_{k,N}\) と表すことができます。
しかし,ダイクストラ法を用いる方法では \(O(V(E+V)\log V)\),ワーシャルフロイド法を用いる方法では \(O(V^3)\) となり,いずれも \(E, V \leq 10^5\) という制約では間に合いません。
ここで,\(d_{1,k} + d_{k,N}\) という式に注目してみましょう。
与えられるグラフは無向グラフであることから,\(d_{i,j} = d_{j,i}\) が成り立ちます。 したがって,\(d_{1,k} + d_{k,N} = d_{1,k} + d_{N,k}\) と変形することができます。
すると,頂点 \(1\) / 頂点 \(N\) から各頂点までの最短路長を求めれば,\(d_{1,k} + d_{N,k}\) の値を求めることができます。
以上の考察より,頂点 \(1\) と頂点 \(N\) のそれぞれからダイクストラ法を適用することで,\(O((E+V)\log V)\) でこの問題を解くことができました。
3. サンプルコード
C++ のサンプルコード
#include <iostream>
#include <queue>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = std::uint64_t;
template <class T>
bool chmin(T& a, const T& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
using Edge = std::pair<int, int>;
using Graph = std::vector<std::vector<Edge>>;
// 頂点 start からダイクストラ法使って各頂点までの最短路長を求める
std::vector<int> dijkstra(const Graph& graph, int start) {
std::vector<int> dist(graph.size(), 1000000010);
dist[start] = 0;
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pque;
pque.emplace(0, start);
while (!pque.empty()) {
auto [now_cost, now] = pque.top();
pque.pop();
if (dist[now] < now_cost) continue;
for (auto [to, cost] : graph[now]) {
if (chmin(dist[to], now_cost + cost)) {
pque.emplace(now_cost + cost, to);
}
}
}
return dist;
}
int main() {
int n, m;
std::cin >> n >> m;
Graph graph(n);
rep(i, m) {
int a, b, c;
std::cin >> a >> b >> c;
--a;
--b;
graph[a].emplace_back(b, c);
graph[b].emplace_back(a, c);
}
// 頂点 1 からの最短路長
const auto& from_1 = dijkstra(graph, 0);
// 頂点 N からの最短路長
const auto& from_n = dijkstra(graph, n - 1);
for (int i = 0; i < n; ++i) {
std::cout << from_1[i] + from_n[i] << "\n";
}
}
Python のサンプルコード
import heapq
def main():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
a, b, c = map(int, input().split())
a -= 1
b -= 1
graph[a].append((b, c))
graph[b].append((a, c))
# 頂点 k からダイクストラ法で各頂点までの最短路長を求める
def dist_from(k: int):
pque = []
dist = [10 ** 9] * n
dist[k] = 0
heapq.heappush(pque, (0, k))
while len(pque) > 0:
now_cost, now = heapq.heappop(pque)
if now_cost > dist[now]:
continue
for to, cost in graph[now]:
if now_cost + cost < dist[to]:
dist[to] = now_cost + cost
heapq.heappush(pque, (now_cost + cost, to))
return dist
from_first = dist_from(0) # 頂点 1 からの最短路長
from_last = dist_from(n - 1) # 頂点 N からの最短路長
for i in range(n):
print(from_first[i] + from_last[i])
if __name__ == "__main__":
main()
posted:
last update: