Spaghetti Source logo

単一始点最短路 (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

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.12.22 23:22:25.