最短路徑

單點源最短路徑

求出一個點到所有點的最短路徑

多點源最短路徑

求出所有點對的最短路徑

鬆弛

Relaxation

對於兩個點 \(u\)、\(v\)，設其之間的邊權為 \(w_{u,v}\)

若起點到它們的距離 \(d_u\)、\(d_v\) 滿足\(d_u+w_{u, v}<d_v\)，
即可把 \(d_v\) 更新成 \(d_u+w_{u, v}\)，使 \(u\) 到 \(v\) 的距離變短，

這個動作就叫鬆弛

Bellman-Ford algorithm

• 將起點最短路徑長設為 0，其餘長度為無限大
• 枚舉每條邊，嘗試每條邊是否可進行鬆弛

若第 \(V\) 次枚舉時仍有邊可以鬆弛，即表示圖中有負環；
否則，表示所有點已為最短路徑

時間複雜度 \(O(VE)\)

Dijkstra algorithm

• 將起點最短路徑長設為 0，其餘長度為無限大
• 在所有已找到最短路徑的點中，尋找所有往外的邊中權重最小者延伸

最糟情況下每條邊都需被鬆弛一次

時間複雜度 \(O(E\ log\ E)\)

cin >> n >> m >> s;
 
for (int i = 1; i <= n; i++)
    dis[i] = 1e18;
dis[s] = 0;
 
int a, b, c;
while (m--)
    cin >> a >> b >> c, edge[a].push_back({b, c});
 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while (!pq.empty())
{
    int u = pq.top().second, d = pq.top().first;
    pq.pop();
 
    if (vis[u])
        continue;
    vis[u] = true;
 
    for (auto p : edge[u])
        if (!vis[p.first] && d + p.second < dis[p.first])
            dis[p.first] = d + p.second, pq.push({dis[p.first], p.first});
}
 
for (int i = 1; i <= n; i++)
    cout << dis[i] << " \n"[i == n];

Floyd-Warshall algorithm

動態規劃

• 令 \(dp_{i,j}\) 為 \(i\) 到 \(j\) 的最短路徑長，
• 將 \(dp_{i, j}\) 設為 \(w_{i,j}\)，\(dp_{i, i}\) 設為 0
• \(dp_{i, j} = min(dp_{i,k}+dp_{k, j}, dp_{i, j})\)

時間複雜度 \(O(V^3)\)

cin >> n >> m;
 
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        dis[i][j] = 2e18;
for (int i = 1; i <= n; i++)
    dis[i][i] = 0;
 
int u, v, w;
while (m--)
    cin >> u >> v >> w, dis[u][v] = min(dis[u][v], w);
 
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
 
for (int i = 1; i <= n; i++)
    if (dis[i][i] < 0)
        cout << "-1\n";
 
for (int i = 1; i <= n; i++, cout << '\n')
    for (int j = 1; j <= n; j++)
        cout << dis[i][j] << ' ';