11-图论/03-最短路

最短路

最短路径问题：给定带权图，求两点间权值和最小的路径。

Floyd 算法

全源最短路。动态规划思想，枚举中间点进行松弛。

int dis[MAXN][MAXN]; // dis[i][j] = i 到 j 的最短距离，初始为 INF

for (int i = 1; i <= n; i++)
    dis[i][i] = 0;

void floyd(int n)
{
    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]);
}

时间复杂度：[math]\displaystyle{ O(n^3) }[/math]，适合 [math]\displaystyle{ n \le 500 }[/math]。

Dijkstra 算法

单源最短路，适用于非负边权图。每次选当前距离最小的点松弛邻点。

暴力版

int dis[MAXN];
bool vis[MAXN];

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == 0 || dis[j] < dis[u]))
                u = j;
        vis[u] = true;
        for (auto [v, w] : g[u])
            if (!vis[v])
                dis[v] = min(dis[v], dis[u] + w);
    }
}

时间复杂度：[math]\displaystyle{ O(n^2) }[/math]。

优先队列优化版

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, s});

    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dis[u]) continue; // 旧数据跳过
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
    }
}

时间复杂度：[math]\displaystyle{ O(m\log m) }[/math]。

Bellman-Ford 与 SPFA

可处理负权边，SPFA 是 Bellman-Ford 的队列优化版。

// SPFA
int dis[MAXN], cnt[MAXN];
bool inq[MAXN];

bool spfa(int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    inq[s] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return false; // 存在负环
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = true;
                }
            }
    }
    return true; // 无负环
}