最短経路問題まとめ
最短経路問題におけるグラフの表現方法、BFS、ダイクストラ法、ベルマンフォード法、ワ―シャルフロイド法についてまとめた。
(1)グラフの表現方法
(1)-[1]重みなしグラフ
重みなしグラフとは、グラフの辺の重みがすべて1のグラフである。
(1)-[1]-<1> 隣接リスト
重みなしグラフは隣接リストを使って表される。
隣接リストとは各頂点についてその頂点に直接つながっている頂点を列挙したものである。
下のグラフについて考える。
このグラフを隣接リストで表すと次のようになる。
0 : 3
1 : 2 , 3
2 : 1
3 : 0 , 1 , 4 , 7
4 : 3 , 7
5 : 6
6 : 5
7 : 3 , 4
この隣接リストは次のように2次元配列で表せる。
int V = 8;//頂点数
vector<vector<int>>G(V);//隣接リストを表す2次元配列
G = { {3},
{2,3},
{1},
{0,1,4,7},
{3,7},
{6},
{5},
{3,4} };G[i]には頂点iに繋がっている頂点が列挙されているとみると、これで隣接リストが表現できたことになる。
競プロの問題で重みなしグラフが与えられるときは、隣接リストが与えられるときもあれば、次のようにつながっている頂点のペアが列挙されて与えられるときもある。
[例]グラフ1
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6
1行目の8は頂点数、7は辺の数である。2行目以降は各辺がつなぐ2つの頂点が書かれている。
このような入力から隣接リストを作る方法は以下の通りである。
int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<int>>G(V);//隣接リスト
for (int i = 0 ; i < E ; i++) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}隣接リストはG[i]にiとつながっている頂点が列挙されているので上の方法で隣接リストを作成できた。
(1)-[2] 重み付きグラフ
重み付きグラフとは、辺に重みが付いているグラフのことである。
(1)-[2]-<1> 隣接リスト
重み付きグラフを隣接リストで表すには辺と重みをペアで扱う必要がある。
下のようなグラフを考える。
0 : (1,1) , (2,4) , (3,2)
1 : (0,1) , (3,3)
2 : (0,4) , (3,50) , (4,2)
3 : (0,2) , (1,3) , (2,50) , (4,6)
4 : (2,2) , (3,6) , (5,2)
5 : (4,2)
6 : (7,3)
7 : (6,3)
それぞれのかっこの前半は繋がっている頂点、後半は繋げている辺の重みである。
この隣接リストはpairの2次元配列で次のように表せる。
#define mp make_pair
int V = 8;//辺の数
vector<vector<pair<int, int>>>G;//隣接リスト
G = { {mp(1,1) , mp(2,4) , mp(3,2)},
{mp(0,1) , mp(3,3)},
{mp(0,4) , mp(3,50) , mp(4,2)},
{mp(0,2) , mp(1,3) , mp(2,50) , mp(4,6)},
{mp(2,2) , mp(3,6) , mp(5,2)},
{mp(4,2)},
{mp(7,3)},
{mp(6,3)} };問題で重み付きグラフが与えられるときは次のように与えられることが多い。
[例]グラフ2
8 9
0 1 1
0 3 2
0 2 4
1 3 3
2 3 50
2 4 2
3 4 6
4 5 2
6 7 3
1行目の8は頂点数、9は辺の数である。
2行目からは頂点、その頂点と繋がっている頂点、辺の重みが空白区切りで与えられる。
この入力から隣接リストは次のように作る。
#define mp make_pair
int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<pair<int, int>>>G(V);//隣接リスト
for (int i = 0; i < E; i++) {
int a, b, cost;
cin >> a >> b >> cost;
G[a].push_back(mp(b, cost));
G[b].push_back(mp(a, cost));
}
(1)-[2]-<2> 隣接行列
隣接行列はV*Vの行列でグラフを表す方法である。主にワ―シャルフロイド法で用いられる。
隣接行列をGとすると、頂点iと頂点jが繋がっているときG[i][j]を頂点iと頂点jを結ぶ辺の重みに、繋がっていないときはG[i][j]を非常に大きい値しておく。ただしi=jのときはG[i][j]=0にする。
グラフ2を隣接行列で表すと次のようになる。
int INF = 1000000000;
int V = 8;//頂点数
vector<vector<int>>G(V, vector<int>(V));//V*Vの隣接行列
G = { { 0 , 1 , 4 , 2 ,INF,INF,INF,INF},
{ 1 , 0 ,INF, 3 ,INF,INF,INF,INF},
{ 4 ,INF, 0 , 50, 2 ,INF,INF,INF},
{ 2 , 3 , 50, 0 , 6 ,INF,INF,INF},
{INF,INF, 2 , 6 , 0 , 2 ,INF,INF},
{INF,INF,INF,INF, 2 , 0 ,INF,INF},
{INF,INF,INF,INF,INF,INF, 0 , 3 },
{INF,INF,INF,INF,INF,INF, 3 , 0 } };次のような入力から隣接行列は次のように作る。
[例]グラフ2
8 9
0 1 1
0 3 2
0 2 4
1 3 3
2 3 50
2 4 2
3 4 6
4 5 2
6 7 3
int INF = 1000000000;
int V;//頂点数
int E;//辺の数
cin >> V >> E;
vector<vector<int>>G(V, vector<int>(V,INF));//V*Vの隣接行列。INFで初期化
for (int i = 0; i < V; i++) {
G[i][i] = 0;
}
for (int i = 0; i < E; i++) {
int a, b, cost;
cin >> a >> b >> cost;
G[a][b] = cost;
G[b][a] = cost;
}
(2)BFS（幅優先探索）
BFSは重みなしグラフの最短経路を求めるときに使われる。
[例]グラフ1における頂点0から他の各頂点への最短距離を求める。たどりつけない場合はINFにする。
int INF = 1000000000;
int V = 8;//頂点数
int E = 7;//辺の数
vector<vector<int>>G(V);//隣接リスト
G = { {3},
{2,3},
{1},
{0,1,4,7},
{3,7},
{6},
{5},
{3,4} };
int start = 0;//スタート位置
vector<int>dist(V, INF);//startからの距離を入れる配列。INF(未訪問)で初期化
queue<int> que;
dist[start] = 0;
que.push(start);
//BFS
while (!que.empty()) {
int v = que.front();
que.pop();
for (int nv : G[v]) {
if (dist[nv] != INF)continue;
dist[nv] = dist[v] + 1;
que.push(nv);
}
}これでdist[i]には頂点0から頂点iまでの最短距離（たどりつけない場合はINF）が入っている。distの中身は{0, 2, 3, 1, 2, INF, INF, 2}になった。
BFSでは1つの頂点からの他の全頂点への最短距離がO(V+E)で求まる。
(3)ダイクストラ法
ダイクストラ法は、負の重みが存在しない重み付きグラフの最短経路を求めるときに使われる。
[例]グラフ2において頂点0から各頂点までの最短経路を求める。たどりつかない場合はINFにする。
#define mp make_pair
#define P pair<int,int>
int INF = 1000000000;
int V = 8;//辺の数
vector<vector<pair<int, int>>>G(V);//隣接リスト
G = { {mp(1,1) , mp(2,4) , mp(3,2)},
{mp(0,1) , mp(3,3)},
{mp(0,4) , mp(3,50) , mp(4,2)},
{mp(0,2) , mp(1,3) , mp(2,50) , mp(4,6)},
{mp(2,2) , mp(3,6) , mp(5,2)},
{mp(4,2)},
{mp(7,3)},
{mp(6,3)} };
int start = 0;//スタート位置
vector<int>dist(V, INF);//startからの距離を入れる配列。INF(未訪問)で初期化
dist[start] = 0;
priority_queue<P, vector<P>, greater<P>>que;//少ない値を優先するプライオリティキューを宣言
que.push(mp(dist[start], start));
while (!que.empty()) {
P p = que.top();
int v = p.second;
que.pop();
if (dist[v] < p.first)continue;
for (int i = 0; i < G[v].size(); i++) {
P e = G[v][i];
int u = e.first, cst = e.second;
if (dist[u] > dist[v] + cst) {
dist[u] = dist[v] + cst;
que.push(mp(dist[u], u));
}
}
}これでdist[i]に頂点0から頂点iまでの最短距離（たどりつかないときはINF）が入った。
distの中身は{0, 1, 4, 2, 6, 8, INF, INF}になった。
ダイクストラ法では、1つの頂点から他の全頂点までの最短経路を
O(ElogV)で求められる。
(4)ベルマンフォード法
ベルマンフォード法は、負の重みをもつ辺が存在するグラフの最短経路問題で使われる。
下のグラフを考える。
グラフ3の隣接リストは次のようになる。
#define mp make_pair
#define P pair<int,int>
int V = 8;//頂点の数
vector<vector<P>>G(V);
G = {
{mp(1,1),mp(2,8)},
{mp(2,2),mp(3,3)},
{mp(3,-3)},
{},
{mp(6,1)},
{mp(4,-4)},
{mp(5,2),mp(7,3)},
{}
};グラフ3で、頂点4→頂点6→頂点5 の順に周り続ければコストを無限に小さくできる。このような全体の重みが負である閉路のことを負閉路という。負閉路が存在するとおかしくなるのでそのようなときは例外処理をする必要がある。
[例]グラフ3で頂点0から各頂点までの最小コストを求める。
#define mp make_pair
#define P pair<int,int>
#define INF 100000000
struct edge//辺を表す構造体
{
int from, to;
int cost;
};
vector<int> bellman_ford(int start, vector<vector<P>>G){
//startから各点への最短距離を配列で返す
//辿り着けなかったらINFにする
//startから負の閉路に到達できたら空の配列を返す
int V = G.size();
vector<int>dist(V, INF);
dist[start] = 0;
vector<edge> es;
for (int i = 0; i < V; i++) {
for (int j = 0; j < G[i].size(); j++) {
edge tmpes;
tmpes.from = i;
tmpes.to = G[i][j].first;
tmpes.cost = G[i][j].second;
es.push_back(tmpes);
}
}
bool flag = true;
for (int i = 0; i < V; i++) {
for (auto& e : es) {
if (dist[e.from] < INF && dist[e.from] + e.cost < dist[e.to]) {
if (i == V - 1) {
flag = false;
}
dist[e.to] = dist[e.from] + e.cost;
}
}
}
if (flag == true) {
return dist;
}
else {
dist.clear();
return dist;
}
}
int main() {
int V = 8;//頂点の数
vector<vector<P>>G(V);
G = {
{mp(1,1),mp(2,8)},
{mp(2,2),mp(3,3)},
{mp(3,-3)},
{},
{mp(6,1)},
{mp(4,-4)},
{mp(5,2),mp(7,3)},
{}
};
int start = 0;
vector<int>dist(V);
dist = bellman_ford(start, G);
}これでdist[i]に頂点0から頂点iまでの最小のコストが入った。
今、distの中身は
{0, 1, 3, 0, INF, INF, INF, INF} である。
また、例えばスタート地点を4にすると頂点4から負閉路に到達できるためdistは空の配列になる。
ベルマンフォード法では1つの頂点から他の全頂点までの最短距離（最小コスト）が、O(VE)で求まる。
(5)ワーシャルフロイド法
ワーシャルフロイド法は、全ての2頂点間の最短経路を求めることができる。
隣接行列を用いる。
[例]グラフ2の全ての2頂点間の最短経路を求める。（たどりつけない場合はINFにする。）
int INF = 1000000000;
int V = 8;//頂点数
vector<vector<int>>G(V, vector<int>(V));//V*Vの隣接行列
G = { { 0 , 1 , 4 , 2 ,INF,INF,INF,INF},
{ 1 , 0 ,INF, 3 ,INF,INF,INF,INF},
{ 4 ,INF, 0 , 50, 2 ,INF,INF,INF},
{ 2 , 3 , 50, 0 , 6 ,INF,INF,INF},
{INF,INF, 2 , 6 , 0 , 2 ,INF,INF},
{INF,INF,INF,INF, 2 , 0 ,INF,INF},
{INF,INF,INF,INF,INF,INF, 0 , 3 },
{INF,INF,INF,INF,INF,INF, 3 , 0 } };
//ワーシャルフロイド
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
}こうするとGは
0 1 4 2 6 8 INF INF
1 0 5 3 7 9 INF INF
4 5 0 6 2 4 INF INF
2 3 6 0 6 8 INF INF
6 7 2 6 0 2 INF INF
8 9 4 8 2 0 INF INF
INF INF INF INF INF INF 0 3
INF INF INF INF INF INF 3 0
となり、G[i][j]が頂点iと頂点jの最短経路を表している。
ワーシャルフロイド法は全ての2頂点間の最短経路を
O(V*V*V)で求めることができる。
また、ワーシャルフロイド法は、負の重みの辺がある場合にも使える。負の閉路がある場合にはG[i][j](i=j)の値が負になるので負の閉路の判定もできる。
負の経路があるときワーシャルフロイド法ではINFの値が変えられる可能性があるため注意が必要である。（INFの判定をINFより少し小さい値で行うなど。）
