Bellman–Ford法とDijkstra法で最短経路問題を解く

(2020-04-01)

Bellman–Ford法とDijkstra法で最短経路問題を解く。

Bellman-Ford法

始点の距離が0、それ以外の頂点の距離が無限大な初期状態から、 全辺を見て各辺を通るとしたときに現在の距離を下回るなら更新する、というのを繰り返すアルゴリズム。 辺の重みは負でも問題ないが、総和が負の値になる閉路が存在する場合、そこで無限ループしてしまうので決まらない。 その場合を除けば、頂点の数を|V|、辺の数を|E|とすると、繰り返しは|V|-1回で終わり、計算量はO(|V||E|)になる。

Bellman-Ford法

Dijkstra法

同じく始点の距離が0、それ以外の頂点の距離が無限大な初期状態から、 まだ選ばれていない頂点の中から最小の距離のものを1つ選んでその最短距離を確定させ、そこから伸びている辺を見て更新していく、というのを繰り返す。 Bellman-Ford法が全ての頂点から同時に探索するのに対してDijkstra法は始点から着実に進んでいくイメージ。 頂点を選ぶ/取り除くのにO(log|V|)かかる二分ヒープのpriority queueで実装すると計算量はO((|E|+|V|)log|V|)となる。 Bellman-Ford法より高速だが、負の重みがあると選んだ頂点の現在の距離が最短であることが確定しないので適用できない。

Dijkstra法

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

まずはBellman-Ford法で解く。繰り返しを最大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];
    }
};

次にDijkstra法で解く。価格と共に乗継数を持ち超過したルートは無視することで、最安でなくても乗継数が少ないルートも採用されるようにする。 実行時間は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;
    }
};

参考

Bellman-Ford法: 負の重みのエッジを含むグラフにおける最短経路

ダイクストラ法

Dijkstra’s algorithm - Wikipedia