查看“︁11-图论/03-最短路”︁的源代码


== 最短路 ==

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

== Floyd 算法 ==

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

<syntaxhighlight lang="cpp">
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]);
}
</syntaxhighlight>

时间复杂度：<math>O(n^3)</math>，适合 <math>n \le 500</math>。

== Dijkstra 算法 ==

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

=== 暴力版 ===

<syntaxhighlight lang="cpp">
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);
    }
}
</syntaxhighlight>

时间复杂度：<math>O(n^2)</math>。

=== 优先队列优化版 ===

<syntaxhighlight lang="cpp">
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});
            }
    }
}
</syntaxhighlight>

时间复杂度：<math>O(m\log m)</math>。

== Bellman-Ford 与 SPFA ==

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

<syntaxhighlight lang="cpp">
// 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; // 无负环
}
</syntaxhighlight>

[[Category:图论]]
[[Category:三三文档]]