#创 OJ 计划# 一文搞懂最短路
2025-08-07 19:54:30
发布于：浙江
全部评论 4
【B3647】Floyd 算法
作者
一扶苏一
扶咕咕
发布时间
2022-11-23 19:40
分类
题解 B3647
【B3647】Floyd 算法
Preface
这是我在大学“数据结构”课程的“翻转课堂”活动的授课任务，即向同学讲解 Floyd 算法。因为课堂的听众不全有竞赛经历，所以我事实上在讲课的前半部分通过几道例题简单介绍了动态规划算法作为引入，在本文中略去。如果你还不了解动态规划和“阶段”“状态”等相关理论，可以先通过课件了解动态规划。完整课件可以点击这里下载。对本文和课件的转载必须注明作者和出处。
Floyd-Warshal Algorithm 是一个基于动态规划的全源最短路算法。它可以高效地求出图上任意两点之间的最短路。
Preliminaries
如无特殊约定，本文用 n 表示图的顶点数，m 表示边数。一张带权有向图被定义为 (V,E,w)，其中 V 是点集，E 是边集，w:E→R 是边集向实数集的映射，称为边权。根据需要，这一映射可能是向非负实数集的。我们的研究着眼于带权有向图上的全源最短路。在无向图上，只需要把边拆成两条有向边即可。我们用如下的邻接矩阵结构存图：
G
u,v
={
x<∞,
∞,
there exists an edge connecting u and vwith weight x,
there are not any edges connecting u and v directly.
,for u
=vG
u,u
=0约定忽略图的自环，重边仅保留权值最小的一条。
A Rough Work
我们首先考虑边权均非负的情况。采用动态规划的方法解决这一问题：设 f
k,u,v
表示当只考虑编号不大于 k 的顶点和 u,v 自身时，u 到 v 的最短路，即要求 u 到 v 的路径上的顶点（不包括 u,v 自身）编号不大于 k，考察此时的最短路。初始状态显然有 f
0,u,v
=G
u,v
。考虑计算 f
k,u,v
，只考虑 u,v 自身和编号不大于 k 的顶点，此时的最短路有两种方案：不经过编号为 k 的顶点。则此时的最短路就是 f
k−1,u,v
；
经过编号为 k 的顶点。那么我们此时的最短路会通过 k 号顶点。我们把 u 到 v 的路径拆成 u→k 和 k→v 两条。注意到此时 u 到 k 的路径上的顶点显然应该都小于 k（因为没有负边，走一个点超过两次不会得到任何正收益），k 到 v 的路径同理。于是这两条路径的最短路分别是 f
k−1,u,k
和 f
k−1,k,v
，如图：综合两种情况，转移就是 f
k,u,v
=min(f
k−1,u,v
,f
k−1,u,k
+f
k−1,k,v
)容易写出代码：
for k := 1 to n:
for u := 1 to n:
for v := 1 to n:
f(k,u,v) := min{f(k-1,u,v), f(k-1,u,k)+f(k-1,k,v)}在这里，k 是我们转移中的阶段。
Space Cost Optimization
A Classic Skill
易见在上一部分里我们提出的算法时空复杂度均为 Θ(n
3
)。时间复杂度难以优化，但是注意到我们最后只要 Θ(n
2
) 个信息。于是考虑对空间复杂度进行优化。考察转移：f
k,u,v
=min(f
k−1,u,v
,f
k−1,u,k
+f
k−1,k,v
) 注意到 f
k
的值只与 f
k−1
有关，和再之前的状态无关，且我们最终关心 f
n
，所以 k−2 及以前的状态可以无需记录。采用经典的“滚动数组”的技巧，令 g
1,u,v
表示当前状态的对应 dp 值，g
0,u,v
表示上一阶段的 dp 值。（这就是说，设当前在计算 f
k
，则令 g
1,u,v
=f
k,u,v
，g
0,u,v
=f
k−1,u,v
）。则转移可以写成：g
1,u,v
=min(g
0,u,v
,g
0,u,k
+g
0,k,v
)。注意每个阶段的转移结束之后（即 f
k
的所有状态被计算完毕后），g
1
成了下一个阶段的“上一个阶段”，此时需要用 g
1
替换 g
0
，计算新的 g
1
，写作代码就是for k := 1 to n:
4天前 来自 浙江
0dijkstra 详解
作者
little_sun
发布时间
2018-07-24 18:55
分类
题解 P4779
前言
SPFA算法由于它上限 O(NM)=O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra.
什么是dijkstra?
dijkstra是一种单源最短路径算法,时间复杂度上限为O(n
2
)(朴素),在实际应用中较为稳定;加上堆优化之后更是具有O((n+m)log
2
n)的时间复杂度,在稠密图中有不俗的表现.
dijkstra的原理/流程?
dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
我们把点分成两类,一类是已经确定最短路径的点,称为"白点",另一类是未确定最短路径的点,称为"蓝点"
dijkstra的流程如下:- 初始化dis[start]=0,其余节点的dis值为无穷大.
- 找一个dis值最小的蓝点x,把节点x变成白点.
- 遍历x的所有出边(x,y,z),若dis[y]>dis[x]+z,则令dis[y]=dis[x]+z
- 重复2,3两步,直到所有点都成为白点.
时间复杂度为O(n
2
)
dijkstra为什么是正确的
当所有边长都是非负数的时候,全局最小值不可能再被其他节点更新.所以在第2步中找出的蓝点x必然满足:dis[x]已经是起点到x的最短路径.我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度
图解
(令start=1)
开始时我们把dis[start]初始化为0,其余点初始化为inf 初始化
第一轮循环找到dis值最小的点1,将1变成白点,对所有与1相连的蓝点的dis值进行修改,使得dis[2]=2,dis[3]=4,dis[4]=7 1
第二轮循环找到dis值最小的点2,将2变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[3]=3,dis[5]=4 2
第三轮循环找到dis值最小的点3,将3变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[4]=4 3
接下来两轮循环分别将4,5设为白点,算法结束,求出所有点的最短路径
时间复杂度O(n
2
)
为什么dijkstra不能处理有负权边的情况?
我们来看下面这张图 4
2到3的边权为−4,显然从1到3的最短路径为−2 (1−>2−>3).但在循环开始时程序会找到当前dis值最小的点3,并标记它为白点.
这时的dis[3]=1,然而1并不是起点到3的最短路径.因为3已经被标为白点,所以dis[3]不会再被修改了.我们在边权存在负数的情况下得到了错误的答案.
dijkstra的堆优化?
观察dijkstra的流程,发现步骤2可以优化
怎么优化呢?
我会zkw线段树!我会斐波那契堆!
我会堆!
我们可以用堆对dis数组进行维护,用O(log
2
n)的时间取出堆顶元素并删除,用O(log
2
n)遍历每条边,总复杂度O((n+m)log
2
n)范例代码:
#include<bits/stdc++.h>
const int MaxN = 100010, MaxM = 500010;
struct edge
{
int to, dis, next;
};edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;inline void add_edge( int u, int v, int d )
{
cnt++;
e[cnt].dis = d;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}struct node
{
int dis;
int pos;
bool operator <( const node &x )const
{
return x.dis < dis;
}
};std::priority_queue<node> q;
inline void dijkstra()
{
dis[s] = 0;
q.push( ( node ){0, s} );
while( !q.empty() )
{
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if( vis[x] )
cont4天前 来自 浙江
0
有帮助，赞一个