Skip to content

最短路徑

術語

  • 負邊：權重為負的邊
  • 負環：權重和為負的環
  • 點源：成為起點的點，分成單源頭及多源頭。
  • 鬆弛：單源頭最短路徑中，對於任意兩個點 ，起點 到它們的距離 ，如果 ， 為邊 的權重，我們可以讓 更新為 ，讓 到 的距離縮短，這個動作稱為 "鬆弛"。

Floyd-Warshall Algorithm

為多源頭最短路徑，求出所有點對的最短路徑。 Floyd-Warshall 是一種動態規劃問題，以下是他的 dp 式。

  • 狀態： 代表，若只以點 當中繼點的話， 到 的最短路徑長。
  • 轉移：

  • 基底：

時/空間複雜度皆為 ，利用滾動陣列技巧，空間複雜度可優化至 

1
2
3
4
for (k = 0; k < n; k++)
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            w[i][j] = w[j][i] = min(w[i][j], w[i][k] + w[k][j]);

執行的時候如果 ，代表存在負環，Floyd-Warshall 是可以判斷負環。

單點源最短路徑

求出一個點到所有點的最短路徑，其實就是以起點為根，最短路徑是由父節點鬆弛而來的最短路徑樹。我們找最短路徑，就是一直把鬆弛，直到所有點都不能鬆弛，所有點都獲得最短路徑了。要蓋出最短路徑樹，就只要把點指向最後一次被誰鬆弛就好了。

Bellman-Ford Algorithm

為單點源最短路徑，設起點的最短路徑為 0，其他點為無限大，每次對所有邊枚舉，因為最短路徑不會經過同樣的邊第二次，所以只要執行 輪，複雜度為 。如果執行第 次時還有邊可以鬆弛，代表有負環，Bellman-Ford 也可以當成負環的判斷方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void bellman_ford(int s)
{
    d[s] = 0;
    p[s] = s;
    for (int i = 0; i < V - 1; i++)
    {
        for (int ss = 0; ss < V; ss++)
        {
            for (auto tt : v[ss])
            {
                if (d[ss] + w[ss][tt] < d[tt])
                {
                    d[tt] = d[ss] + w[ss][tt];
                    p[tt] = ss;
                }
            }
        }
    }
}
bool has_negative_cycle()
{
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (d[i] + w[i][j] < d[j])
                return true;
        }
    }
    return false;
}

此演算法還有一個優化版本叫做 Shortest Path Faster Algorithm (SPFA)，他的做法是枚舉起點是鬆弛過的邊，以鬆弛過的點除非被重新鬆弛，否則不會更動。預期複雜度為 ，不過最差狀況仍為 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct Edge
{
    int t;
    long long w;
    Edge(){};
    Edge(int _t, long long _w) : t(_t), w(_w) {}
};

bool SPFA(int st)
{
    vector<int> cnt(n, 0);
    bitset<MXV> inq(0);
    queue<int> q;

    q.push(st);
    dis[st] = 0;
    inq[st] = true;
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        inq[cur] = false;
        for (auto &e : G[cur])
        {
            if (dis[e.t] <= dis[cur] + e.w)
                continue;
            dis[e.t] = dis[cur] + e.w;
            if (inq[e.t])
                continue;
            ++cnt[e.t];
            if (cnt[e.t] > n)
                return false; // negtive cycle
            inq[e.t] = true;
            q.push(e.t);
        }
    }
    return true;
}

Dijkstra’s Algorithm

同樣為單點源最短路徑，他的想法和 Prim's Algorithm 類似，每次把離樹根最近的點加入最短路徑樹裡，並把所有與該點相連的邊鬆弛，已經加入的點不會在被鬆弛。

使用 priority_queue 的複雜度為 ，使用費波那契堆，複雜度為 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct edge
{
    int s, t;
    LL d;
    edge(){};
    edge(int s, int t, LL d) : s(s), t(t), d(d) {}
};

struct heap
{
    LL d;
    int p; // point
    heap(){};
    heap(LL d, int p) : d(d), p(p) {}
    bool operator<(const heap &b) const { return d > b.d; }
};

int d[N], p[N];
vector<edge> edges;
vector<int> G[N];
bitset<N> vis;

void dijkstra(int ss)
{
    priority_queue<heap> Q;
    for (int i = 0; i < V; i++)
        d[i] = INF;
    d[ss] = 0;
    p[ss] = -1;
    vis.reset() : Q.push(heap(0, ss));
    heap x;
    while (!Q.empty())
    {
        x = Q.top();
        Q.pop();
        int p = x.p;
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int i = 0; i < G[p].size(); i++)
        {
            edge &e = edges[G[p][i]];
            if (d[e.t] > d[p] + e.d)
            {
                d[e.t] = d[p] + e.d;
                p[e.t] = G[p][i];
                Q.push(heap(d[e.t], e.t));
            }
        }
    }
}

而 Dijkstra’s Algorithm 不能處理負邊，原因是一旦點加入最短路徑樹，就不會再被更新，以維持良好複雜度，負邊會破壞此規則。

整理

演算法 Floyd-Warshall Bellman-Ford SPFA Dijkstra
點源 多點源 單點源 單點源 單點源
時間複雜度 期望複雜度 使用 priority_queue
判斷負環 O X X X
處理負邊 O X X X

例題練習