ダイクストラ法（Dijkstra法）は、グラフ上で単一始点（終点）の最短経路を効率的に求めるアルゴリズムです。
本記事ではC++で使えるダイクストラ法のライブラリを実装します。
※なお、今回のライブラリは Graph ライブラリが前提となっています。
以下リンクからコピペしてご使用ください↓
・グラフ構造体 をC++で実装してみた
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
dijkstra<T>(g, starts) |
グラフ g の各頂点に対して、starts から各頂点への最短距離を計算 |
$O(E \ log \ V)$ |
実装したコード
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
// 戻り値の配列retは、「ret[i] := starts から i への最短距離」となります
template<typename T = long long> // costの型
vector<T> dijkstra(Graph<T> &g, vector<int> starts){
// {startsからの最短コスト、場所}の配列
vector<T> ret(g.size_n(), T(100100100100100100));
// 最短距離の短い順に処理するための優先度付きキュー
using P = pair<T, int>;
priority_queue<P, vector<P>, greater<P>> q;
//開始地点を初期化していく
for(int start: starts){
ret[start] = T(0);
q.push({T(0), start});
}
//行けるところ全てを更新していく
while(!q.empty()){
//キューの中から、距離最小のものを取る
int i = q.top().second;
T c = q.top().first;
q.pop();
//もっといいスコアで計算されてるなら、無視
if(ret[i] < c) continue;
ret[i] = c;
for(P &next: g.nexts(i)){
int ni = next.second;
int nc = next.first + c;
//最小コストを更新できるときだけ更新
if(ret[ni] <= nc) continue;
ret[ni] = nc;
q.push({nc, ni});
}
}
return ret;
}
使用例
#include<bits/stdc++.h>
using namespace std;
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
//--ここにDijkstraライブラリ--//
// //
//-------------------------//
int main(void){
// グラフの作成
Graph g(4);
g.add_edge(10, 0, 1); //0 → 1：コスト10の辺を追加
g.add_edge(10, 0, 2); //0 → 2：コスト10の辺を追加
g.add_edge(15, 0, 3); //0 → 3：コスト15の辺を追加
g.add_edge(1, 2, 3); //2 → 3：コスト1の辺を追加
// 0から各頂点への最短距離を求める
vector<long long> dijk = dijkstra(g, {0});
cout << dijk[3] << endl; // 11
}
注意点・Tips
- 頂点番号は
0-indexedで扱っています - コストの型
Tには、long long、int、doubleなどが使えます -
startsから辿り着けない頂点は、最短距離が100100100100100100となっています -
dijkstra(g, {0,2,3})とすれば、多点スタートも可能です - 始点が一つであっても
dijkstra(g, {0})とする必要があることに注意してください
実際に使ってみる
AtCoder Beginner Contest 035 - D問題
#include <bits/stdc++.h>
using namespace std;
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
//---ここにDijkstraライブラリ---//
// //
//---------------------------//
// グローバル変数
int N, M, T;
vector<int> A;
int main(void){
// 入力
cin >> N >> M >> T;
A.resize(N);
for(int i=0;i<N;i++) cin >> A[i];
// 行きと帰りの最短経路を計算するため、辺を逆にしたグラフも作っておく
Graph g(N);
Graph ig(N);
// グラフを構築
for(int i=0;i<M;i++){
int a, b, c;
cin >> a >> b >> c;
a--; // 0-indexedに変換
b--; // 0-indexedに変換
g.add_edge(c, a, b);
ig.add_edge(c, b, a);
}
//各頂点までの往復の最短経路を計算
vector<long long> dijk = dijkstra(g, {0});
vector<long long> idijk = dijkstra(ig, {0});
//各頂点に対して、最短で往復した場合に得られる最大利益を計算
long long ans = 0;
for(int i=0;i<N;i++){
long long cost = dijk[i] + idijk[i];
//そもそも往復できないなら無視
if(cost > T) continue;
ans = max(ans, (T-cost)*A[i]);
}
cout << ans << endl;
}