単一始点最短路 (Dijkstra)

説明

Dijkstra 法は負辺のない単一始点全点間最短距離を求めるアルゴリズムである．

負辺が無いと仮定すると，各時点でもっとも近いところから距離が確定していく．したがって距離順でソートされたヒープを用いると効率よく次々と各点の距離を確定していくことができる．用いるヒープとして普通のヒープを使えば O((V + E) log V) で実行できる．

用いるヒープに関してさまざまな研究が知られており，フィボナッチヒープやラディックスヒープなどを用いることで（理論的には）効率を改善することができるが，ここでは std::priority_queue で容易に実装できる普通のヒープを用いたものを示す．

計算量

O(E log V)

使い方

負辺はないものとする．

const Graph &g

グラフ．負の枝は無いものとする．

int s

始点．

vector<Weight> &dist

各頂点までの距離が入る．

vector<int> &prev

最短路木の親頂点が入る．

ソースコード

void shortestPath(const Graph &g, int s,
    vector<Weight> &dist, vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF); dist[s] = 0;
  prev.assign(n, -1);
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.front(); Q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;
    FOR(f,g[e.dst]) {
      if (dist[f->dst] > e.weight+f->weight) {
        dist[f->dst] = e.weight+f->weight;
        Q.push(Edge(f->src, f->dst, e.weight+f->weight));
      }
    }
  }
}
vector<int> buildPath(const vector<int> &prev, int t) {
  vector<int> path;
  for (int u = t; u >= 0; u = prev[u])
    path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}

Verified

• UVA 117 - The Postal Worker Rings Once (0.002 sec)
• UVA 341 - Non-Stop Travel (0.105 sec)