[L3] 最短路体系

最短路体系

题目

• P5304 旅行者 多源最短路的应用，染色法 / 二进制分组。
• P9751 旅游巴士 类同余最短路，状态扩展的最短路问题。

一、单源最短路

Dijkstra

• Dijkstra：一种求解单源最短路径的算法．无法处理 有负权图。

• 核心原理：贪心。每次锁定当前代价最小的点，它一定是最优的。

• 复杂度：朴素 $O( n^2 + m )$，堆优化 $O( m \log n )$。

当 $m \approx n$ 时 堆优化更高效；当 $m \approx n^{2}$ 时 堆优化反而低效。

Dijkstra 朴素 / 堆优化 模板

▶

Dijkstra - 朴素

ll g[maxn][maxn];

void dijkstra( int s ) 
{
    fill( dist, dist + n + 1, inf );
    dist[s] = 0;
	
    for( int i = 1; i <= n; ++ i ) 
    {
        int u = -1;
        for( int v = 1; v <= n; ++ v ) 
        {
            if( !vis[v] && ( u == -1 || dist[v] < dist[u] ) ) u = v;
        }
        vis[u] = true;
        for( int v = 1; v <= n; ++ v ) 
        {
            dist[v] = min( dist[v], dist[u] + g[u][v] );
        }
    }
}

▶

Dijkstra - 堆优化

struct Edge { int v, w; };
vector< Edge > adj[maxn];

// 优先队列状态 (重载小于号 -> 小根堆)
struct State {
    int u; ll d;
    bool operator < ( const State& oth ) const { return d > oth.d; }
};

void dijkstra( int s ) 
{
    fill( dist, dist + n + 1, inf );
    dist[s] = 0;
    
    priority_queue< State > pq;
    pq.push({ s, 0 });
	
    while( !pq.empty( ) ) 
    {
        auto [u, d] = pq.top( );
        pq.pop( );
        
        if( d > dist[u] ) continue;
		
        for( auto& [v, w] : adj[u] ) 
        {
            if( dist[u] + w < dist[v] ) 
            {
                dist[v] = dist[u] + w;
                pq.push({ v, dist[v] });
            }
        }
    }
}

Bellman-Ford

• Bellman-Ford：一种求解单源最短路的算法，可以处理 有负权图 ，并可以对最短路不存在的情况进行判断。

• SPFA：Bellman-Ford 的队列优化版本。

• 核心原理：松弛。只要一个点的代价变小了，它的邻居就有可能变小。

• 复杂度：Bellman-Ford $O( n \cdot m )$，SPFA $O( k \cdot m )$。

SPFA 复杂度下限等于 Bellman-Ford，因此在 非负权图 上很容易被卡死。
但在处理 有负权图 时，随机数据下优于 Bellman-Ford。

Bellman-Ford / SPFA - BFS 模板

▶

Bellman-Ford

struct Edge { int u, v, w; };
vector< Edge > edges;
ll dist[maxn];
int n, m, s;

bool bellman_ford( int s ) 
{
    fill( dist, dist + n + 1, inf );
    dist[s] = 0;

    bool relaxed;
    for( int i = 1; i <= n; ++ i )
    {
        relaxed = false;
        for( auto &[u, v, w] : edges ) 
        {
            if( dist[u] != inf && dist[u] + w < dist[v] ) 
            {
                dist[v] = dist[u] + w;
                relaxed = true;
                if( i == n ) return true;
            }
        }
        if( !relaxed ) break;
    }
    return false;
}

▶

SPFA - BFS

struct Edge { int v, w; };
vector< Edge > adj[maxn];
ll dist[maxn];
int cnt[maxn];
bool inq[maxn];
int n, m;

bool spfa( int s ) 
{
    fill( dist, dist + n + 1, inf );
    fill( cnt, cnt + n + 1, 0 );
    fill( inq, inq + n + 1, false );

    queue<int> q;
    q.push( s ), inq[s] = true;
    dist[s] = 0;

    while( !q.empty( ) ) 
    {
        int u = q.front( ); 
        q.pop( ), inq[u] = false;

        for( auto& [v, w] : adj[u] ) 
        {
            if( dist[u] + w < dist[v] ) 
            {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if( cnt[v] >= n ) return true;
                if( !inq[v] ) q.push( v ), inq[v] = true;
            }
        }
    }
    return false;
}

二、负环与差分约束

SPFA 求负环

• 负环：一条边权之和为负数的回路。

• 核心原理：抽屉原理。若图中不存在负环，最短路径最多包含 $n-1$ 条边。如果某个点被松弛的次数（或入队次数） $\ge n$，则必然存在负环。

• 相关例题：P3199 最小圈：分数规划变换 + 负环判定。

SPFA - DFS 模板

▶

SPFA - DFS

struct Edge { int v, w; };
vector< Edge > adj[maxn];
ll dist[maxn];
bool vis[maxn];
int n, m;

bool spfa( int u ) 
{
    vis[u] = true;
    for( auto& [v, w] : adj[u] ) 
    {
        if( dist[u] + w < dist[v] ) 
        {
            dist[v] = dist[u] + w;
            if( vis[v] ) return true;
            if( spfa( v ) ) return true;
        }
    }
    vis[u] = false;
    return false;
}

差分约束

• 差分约束：求解形如 $X_u - X_v \leq w$ 不等式组，利用最短路算法寻找一组可行解的方法。

• 核心原理：映射（松弛）。利用三角不等式 $dist[v] \le dist[u] + w$ 对偶 $X_v \le X_u + w$。若存在负环，说明不等式组存在逻辑冲突（系统无解）。

$X_{v} \leq X_{u} + w$，连一条 $u \to v$ 的权值为 $w$ 的边。
若出现 $X_{u} - X_{v} \geq w$ 的情况，则两侧乘 $-1$ 得到 $X_{v} - X_{u} \leq -w$。
若出现 $X_{u} - X_{v} = w$ 的情况，则拆分成 $X_{u} - X_{v} \leq w$ 和 $X_{v} - X_{u} \geq w$ 即可。

• 相关例题：P1993 小K的农场

三、多源最短路与传递闭包

Floyd 多源最短路

• Floyd：解决多源最短路的算法，适用于点数小的情况（ 时间复杂度 $O(N^3)$ ）。

• 核心原理：动态规划。$dp[k][i][j]$ 表示允许经过前 $k$ 个点中转的最短路径。

• 相关例题：P1119 灾后重建

Floyd 模板

注意：最外层循环必须是中转点 $k$。

▶

Floyd

ll d[505][505];
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 ) 
		if( d[i][k] != inf && d[k][j] != inf ) 
			d[i][j] = min( d[i][j], d[i][k] + d[k][j] );
}

Floyd 传递闭包

• 传递闭包：用于推导图中节点间连通性或偏序关系（如“A大于B，B大于C $\to$ A大于C”）。

• 核心原理：将 Floyd 最短路公式中的求和与取 $\min$ 运算，替换为逻辑与（&）和逻辑或（|）运算：d[i][j] |= d[i][k] & d[k][j]。

• 相关例题：P1119 灾后重建

四、状态空间转换

分层图

• 分层图：当决策包含 “特殊能力”（如 $K$ 次免费、消除某条边）时，使用的一种 扩展状态 的建图方法。

• 核心原理：状态拓展。将状态从一维的点 $u$ 升维到二维 $(u, k)$。同层正常连边代价为 $w$，跨层连边代表使用能力，代价通常为 $0$。

• 相关例题：P4568 飞行路线 | P1073 最优贸易

同余最短路

• 同余最短路：利用模运算将无限的值域空间压缩到有限的同余环中。

解决极大容量的完全背包可行性问题。

• 核心原理：周期性覆盖。选取 $m = \min(a_i)$ 为模数，若模 $m$ 余 $r$ 的最小值 $dist[r]$ 被凑出，则所有 $dist[r] + k \cdot m$ 均可被凑出。因此将 $dist[r]$ 作为状态，边权为 $a_k$，在图上跑最短路。

• 相关例题：P2371 墨墨的等式 | ABC443F Non-Increasing Number

五、其他派生

次短路

• 次短路：求解图上两点间的第二短路径。

• 核心原理：状态扩展。每个节点维护两个距离值 $dist_1$ (最短) 和 $dist_2$ (次短)。

• 相关例题：P2829 大逃离

最短路图

• 最短路图：除去原图中所有非最优的边，剩下的边构成一个 DAG，是处理 “最短路方案数” 或 “公共路径” 的骨架模型。

• 核心原理：三角等式判定。若边 $(u, v)$ 在起点到终点的最短路上，必定满足：$dist_{start}[u] + w(u, v) + dist_{end}[v] == dist_{start}[end]$。