ベルマンフォード法とダイクストラ法とワーシャルフロイド法で最短経路問題を解く
algorithmベルマンフォード法とダイクストラ法ワーシャルフロイド法で最短経路問題を解く。
ベルマンフォード法
始点の距離が0、それ以外の頂点の距離が無限大な初期状態から、
全辺を見て各辺を通るとしたときに現在の距離を下回るなら更新する、というのを繰り返すアルゴリズム。
辺の重みは負でも問題ないが、総和が負の値になる閉路が存在する場合、そこで無限ループしてしまうので決まらない。
その場合を除けば、頂点の数を|V|、辺の数を|E|とすると、繰り返しは|V|-1回で終わり、計算量はO(|V||E|)になる。
ダイクストラ法
同じく始点の距離が0、それ以外の頂点の距離が無限大な初期状態から、
まだ選ばれていない頂点の中から最小の距離のものを1つ選んでその最短距離を確定させ、そこから伸びている辺を見て更新していく、というのを繰り返す。
ベルマンフォード法が全ての頂点から同時に探索するのに対してこちらは始点から着実に進んでいくイメージ。
頂点を選ぶ/取り除くのにO(log|V|)かかる二分ヒープのpriority queueで実装すると計算量はO((|E|+|V|)log|V|)となる。
ベルマンフォード法より高速だが、負の重みがあると選んだ頂点の現在の距離が最短であることが確定しないので適用できない。
ワーシャルフロイド法
2点間ではなく全ての頂点間の最短経路を求めるアルゴリズム。
i→j間の最短経路上に頂点kがあると仮定した場合その経路はi→kの最短経路とk→jの最短経路を繋げたものになることを利用し、
ある2点間の最短経路上に各頂点があるとした場合を総当たりする。
計算量はO(|V|^3)とかなり遅いが次のように単純な3重ループで実装できる。
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
costs[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
Cheapest Flights Within K Stops - LeetCode
乗継K回以内のフライトの最安値を返す問題。
There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.
Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
まずはベルマンフォード法で解く。繰り返しを最大K+1回で止めることで乗継K回以内という制約をかけている。 実行時間は128ms。
class Solution {
public:
int inf = 1000 * 100 + 1;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector costs(n, inf);
costs[src] = 0;
int step = min(K + 1, n - 1);
for (int i = 0; i < step; i++) {
vector nextCosts = costs;
for(vector<int> flight: flights) {
nextCosts[flight[1]] = min(nextCosts[flight[1]], costs[flight[0]] + flight[2]);
}
costs = nextCosts;
}
if (costs[dst] == inf) {
return -1;
}
return costs[dst];
}
};
次にダイクストラ法で解く。価格と共に乗継数を持ち超過したルートは無視することで、最安でなくても乗継数が少ないルートも採用されるようにする。 実行時間は172msとあまり振るわず。
[Java/Python] Priority Queue Solution - LeetCode Discuss
class Solution {
public:
int inf = 1000 * 100 + 1;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
map<int, map<int, int>> costs;
for (vector<int> flight: flights) {
costs[flight[0]][flight[1]] = flight[2]; // [from][to] = cost
}
auto compare = [](vector<int> a, vector<int> b) { return a[1] > b[1]; };
priority_queue<vector<int>, vector<vector<int>>, decltype(compare)> Q(compare);
Q.push({src, 0, 0}); // city, price, stop
while(!Q.empty()) {
vector<int> current = Q.top();
Q.pop();
if (current[0] == dst) {
return current[1];
}
if (current[2] > K) {
continue;
}
for (auto cost: costs[current[0]]) {
Q.push({cost.first, current[1] + cost.second, current[2] + 1});
}
}
return -1;
}
};
最後にワーシャルフロイド法で解いたがTLEになってしまった。
i→j間をstep回以内の乗継で移動する最小コストを、m回以内の乗継でi→l区間を移動する最小コストとstep-m回以内の乗継でl→j区間を移動する最小コストを足して求めている。
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// costs[from][to][step] = min_cost
vector<vector<vector<long>>> costs(n, vector<vector<long>>(n, vector<long>(k+2, INT_MAX)));
for (int i = 0; i < flights.size(); i++) {
costs[flights[i][0]][flights[i][1]][1] = flights[i][2];
}
for (int step = 2; step <= k+1; step++) {
for (int l = 0; l < n; l++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int m = 1; m < step; m++) {
// i --(m steps)--> l --(step-m steps)--> j
costs[i][j][step] = min(costs[i][j][step], min(costs[i][j][step-1], costs[i][l][m] + costs[l][j][step-m]));
}
}
}
}
}
if (costs[src][dst][k+1] == INT_MAX) return -1;
return costs[src][dst][k+1];
}
};