Dijkstra
コードについての説明
非負重みの辺のみからなるグラフに対する単一始点最短経路問題(SSSP) を効率よく解くアルゴリズム.
始点からの距離が近いものから順に探索を繰り返す("始点から最も近い頂点"は優先度付きキューを用いて効率よく管理する). ここでヒープとして二分ヒープではなくフィボナッチヒープを用いると, $\O ((m + n) \log n) \rightarrow \O (n \log n + m)$ になる(参考).
また二分ヒープのかわりに Radix Heap を用いた Dijkstra 法の高速化の話もある(参考).
密なグラフ($m = \Theta (n^2)$) については優先度付きキューを使わず一番近い頂点を愚直に計算することで $\O (n^2)$ で解くことができる.
正の整数の重みの辺からなる無向グラフについては単一始点最短経路問題が線形時間で解けることが知られている.
"Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time" [Thorup 1997]
(関数)
add_edge$(u, v, cost)$ : $u$ から $v$ に向かう重み $cost$ の有向辺を追加する
solve$(s)$ : $s$ を始点として各頂点までの最短距離を求める
時間計算量: $\O ((n + m) \log n)$
コード
template<typename T> class Dijkstra {
private:
struct edge{
int to; T cost;
};
int V;
vector<vector<edge> > G;
vector<T> d;
using pti = pair<T,int>;
public:
Dijkstra(int node_size) : V(node_size), G(V), d(V, numeric_limits<T>::max()){}
void add_edge(int u,int v,T cost){
G[u].push_back((edge){v,cost});
}
void solve(int s){
priority_queue<pti,vector<pti>,greater<pti> > que;
d[s] = 0;
que.push(pti(0,s));
while(!que.empty()){
pti p = que.top();
que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(auto& w : G[v]){
if(d[w.to] > d[v] + w.cost){
d[w.to] = d[v] + w.cost;
que.push(pti(d[w.to],w.to));
}
}
}
}
};