k-最短路

説明

グラフ G と始点終点の対 (s,t) が与えられたとき，s-t パスの中で k 番目に短いものを求める問題を k-最短路問題という．

この問題に対する最も基本的な解法は，優先度付きキューを用いてダイクストラ調にグラフを探索し，通常なら最短距離が確定した頂点を切り捨てるところを k 個の最短距離が確定した頂点を切り捨てるようにすることである（以下に実装を示した）．この方法で計算量 O(k E log V) が達成できる．多くの応用ではこれで十分だと考えられる．

理論的にはもっと頭の良い解法が提案されており，例えば Eppstein による deviation に基づくアルゴリズムは O(k + E + V log V) を達成する．しかし，このアルゴリズムはパスを管理するデータ構造を持たなければならず，シンプルに実装するのは難しい．そこで以下では Eppstein の方法を参考にしたヒューリスティクスを示す．

方針は次の通り．まず，終点 t を根とする逆向きの最短路木をつくる．点 u から t への最短路長を d[u] であらわす．辺 (u,v) に対し，その重みを c(u,v) - d[u] + d[v] に置き換える．このグラフ上で前述の単純なアルゴリズムを実行すると，終点を優先して距離確定するようになる．この修正により，数値実験では三倍程度高速になることが確かめられた．

なお，置き換えた重みには次のような意味がある．最短路木の上ではこの値は常にゼロであり，最短路木を外れるたびに重みが増加する．経路中で最短路木を外れる辺のことをサイドトラックという．全くサイドトラックを持たない経路は明らかに最短路であり，唯一つのサイドトラックを持つ経路が第二最短路である．k-最短路もできるだけ少なくサイドトラックをすれば計算することができ，Eppstein のアルゴリズムはこの部分をヒープを用いて効率的に管理している．ここではそこをサボって探索していることになる．

計算量

O(k E log V)

ソースコード

Weight k_shortestPath(const Graph &g, int s, int t, int k) {
  const int n = g.size();

  Graph h(n); // make reverse graph
  REP(u, n) FOR(e, g[u])
    h[e->dst].push_back(Edge(e->dst,e->src,e->weight));

  vector<Weight> d(n, INF); d[t] = 0; // make potential
  vector<int> p(n, -1);               // using backward dijkstra
  priority_queue<Edge> Q; Q.push(Edge(t, t, 0));
  while (!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (p[e.dst] >= 0) continue;
    p[e.dst] = e.src;
    FOR(f, h[e.dst]) if (d[f->dst] > e.weight + f->weight) {
      d[f->dst] = e.weight + f->weight;
      Q.push(Edge(f->src, f->dst, e.weight + f->weight));
    }
  }
  int l = 0; // forward dijkstra-like method
  priority_queue<Edge> R; R.push(Edge(-1,s,0));
  while (!R.empty()) {
    Edge e = R.top(); R.pop();
    if (e.dst == t && ++l == k) return e.weight + d[s];
    FOR(f, g[e.dst])
      R.push(Edge(f->src, f->dst, e.weight+f->weight-d[f->src]+d[f->dst]));
  }
  return -1; // not found
}

// simpler method
Weight k_shortestPath(const Graph &g, int s, int t, int k) {
  const int n = g.size();
  vector<Weight> dist[n];
  priority_queue<Edge> Q; Q.push(Edge(-1, s, 0));
  while (!Q.empty()) {
    Edge e = Q.top(); Q.top();
    if (dist[e.dst].size() >= k) continue;
    dist[e.dst].push_back(e.weight);
    FOR(f, g[e.dst]) Q.push(Edge(f->src, f->dst, f->weight+e.weight));
  }
}

Verified

• UVA 10740 - Not the Best (0.070 sec)