最短路知识点总结(Dijkstra,Floyd,SPFA,Bellman-Ford)
1、Dijkstra
单源最短路问题
在带权图 G = (V, E) 中,每条边都有一个权值w_i,即边的长度。路径的长度为路径上所有边权之和。单源最短路问题是指:求源点 s到图中其余各顶点的最短路径。
概述
解决单源最短路径问题常用 Dijkstra 算法,用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心,逐层向外扩展,每次都会取一个最近点继续扩展,直到取完所有点为止。
注意:Dijkstra 算法要求图中不能出现负权边。
算法流程
我们定义带权图 G所有顶点的集合为V,接着我们再定义已确定从源点出发的最短路径的顶点集合为 U,初始集合 U 为空,记从源点 s 出发到每个顶点 vv 的距离为 dist_v,初始 dist_s=0。接着执行以下操作:
- 从 V-U 中找出一个距离源点最近的顶点 v,将 v 加入集合 U,并用 dist_v 和顶点 v 连出的边来更新和 v 相邻的、不在集合 U 中的顶点的 dist;
- 重复第一步操作,直到 V=U或找不出一个从 s出发有路径到达的顶点,算法结束。
如果最后V≠U,说明有顶点无法从源点到达;否则每个 dist_i表示从 出发到顶点i 的最短距离。求图中不能出现负权边。
算法分析
比如说下面这个例子,红色部分代表已经确认是最小的了,而绿色部分则不确定,用红色的来更新绿色的(是不是带有一些贪心的思想和动态规划的思想呢)。算法中每次取最小边就是用了贪心的思想,用已知的来更新未知的就是动态规划思想。
算法演示
接下来,我们用一个例子来说明这个算法。
初始每个顶点的 dist设置为无穷大inf源点M的 dist_M设置为∞。当前 U=∅,V-U中dist最小的顶点是 M。从顶点 M 出发,更新相邻点的 dist。
更新完毕,此时 U={M},V-U中 dist最小的顶点是W。从W出发,更新相邻点的 dist。
更新完毕,此时 U={M,W},V-U中 dist 最小的顶点是 E。从 E出发,更新相邻顶点的 dist。
更新完毕,此时 U={M,W,E},V-U 中 dist 最小的顶点是 X。从 X 出发,更新相邻顶点的 dist。
更新完毕,此时 U={M,W,E,X},V-U中 dist最小的顶点是 D。从 D 出发,没有其他不在集合 U中的顶点。
此时 U=V,算法结束,单源最短路计算完毕。
参考代码
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
int v, min_w = inf; // 记录 dist 最小的顶点编号和 dist 值
for (int j = 0; j < n; ++j) {
if (!vst[j] && dist[j] < min_w) {
min_w = dist[j];
v = j;
}
}
if (min_w == inf) { // 没有可用的顶点,算法结束,说明有顶点无法从源点到达
return false;
}
vst[v] = true; // 将顶点 v 加入集合 U 中
for (int j = p[v]; j != -1; j = e[j].next) {
// 如果和 v 相邻的顶点 x 满足 dist[v] + w(v, x) < dist[x] 则更新 dist[x],这一般被称作“松弛”操作
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
}
}
}
return true; // 源点可以到达所有顶点,算法正常结束
}
优化改进
如果每次暴力枚举选取距离最小的元素,则总的时间复杂度是O(V2)。因为每次只需要取最小的元素,所以可以考虑用堆优化,维护一个小根堆,取出距离最小的顶点,再进行扩展,时间复杂度O((V+E)logV),对于稀疏图的优化效果非常好。
参考代码
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap; // 用 set 来伪实现一个小根堆,并具有映射二叉堆的功能。堆中 pair<int, int> 的 second 表示顶点下标,first 表示该顶点的 dist 值
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
min_heap.insert(make_pair(0, s));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点,说明有顶点无法从源点到达,算法结束
return false;
}
// 获取堆顶元素,并将堆顶元素从堆中删除
auto iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
// 先将对应的 pair 从堆中删除,再将更新后的 pair 插入堆
min_heap.erase(make_pair(dist[x], x));
dist[x] = dist[v] + e[j].w;
min_heap.insert(make_pair(dist[x], x));
}
}
}
return true; // 存储单源最短路的结果
}
2、Floyd
概述
Floyd 算法是一种利用动态规划的思想、计算给定的带权图中任意两个顶点之间最短路径的算法。相比于重复执行多次单源最短路算法,Floyd 具有高效、代码简短的优势,在解决图论最短路题目时比较常用。
算法过程
Floyd 的基本思想是:对于一个顶点个数为 n 的有向图,并有一个n×n 的方阵G(k),除对角元素 Gi,i=0 以外,其他元素 Gi,j(i≠j) 表示从顶点 i 到顶点 j 的有向路径长度。
- 初始时 k=-1,G(−1)=E,E 是图的邻接矩阵,满足如下要求:
- 对于任意两个顶点 i,j若它们之间存在有向边,则以此边权上的权值作为Ei,j;
- 若两个顶点i,j 之间不存在有向边,则 Ei,j 为无穷大 INF。
- 对于阶段 k,尝试在 G(k−1) 中增加一个中间顶点 k,如果通过中间顶点使得最短路径变短了,就更新作为新的G(k) 的结果。
- 累加 k,重复执行步骤 2,直到 k=n。
算法结束后,矩阵 G(n−1) 中的元素就代表着图中任意两点之间的最短路径长度。
算法分析
通常,Floyd 算法用邻接矩阵来实现。空间复杂度为 O(V^2),时间复杂度为O(V^3)。
参考代码
const int inf = 0x3f3f3f3f;
int g[MAX_N][MAX_N]; // 算法中的 G 矩阵
// 初始化 g 矩阵
void init() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
g[i][j] = 0;
} else {
g[i][j] = inf;
}
}
}
}
// 插入一条带权有向边
void insert(int u, int v, int w) {
g[u][v] = w;
}
// 核心代码
void floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][k] + g[k][j] < g[i][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
}
3、SPFA
概述
在 SPFA 算法中,使用d_i表示从源点到顶点 i 的最短路,额外用一个队列来保存即将进行拓展的顶点列表,并用 inq_i 来标识顶点 i是不是在队列中。
- 初始队列中仅包含源点,且源点 s 的 d_s=0。
-
取出队列头顶点 u,扫描从顶点 u 出发的每条边,设每条边的另一端为 v,边 <u,v> 权值为 w,若 d_u+w<d_v,则
- 将 d_v修改为 d_u+w
- 若 vv不在队列中,则将 v入队
- 重复步骤 2 直到队列为空
最终 dd数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
负环判断
在进行 SPFA 时,用一个数组 cnt_i 来标记每个顶点入队次数。如果一个顶点入队次数 cnt_i大于顶点总数 n,则表示该图中包含负环。
运行效率
很显然,SPFA 的空间复杂度为 O(V)。如果顶点的平均入队次数为 k,则 SPFA 的时间复杂度为 O(kE),对于较为随机的稀疏图,根据经验 k一般不超过 4。
SPFA 思想
在一定程度上,可以认为 SPFA 是由 BFS 的思想转化而来。从不含边权或者说边权为 11 个单位长度的图上的 BFS,推广到带权图上,就得到了 SPFA。正如我们前面所说,SPFA 的本质是 Bellman-ford 算法的队列优化。由于 SPFA 没有改变 Bellaman-ford 的时间复杂度,国外一般来说不认为 SPFA 是一个新的算法,而仅仅是 Bellman-ford 的队列优化。
参考代码
bool inq[MAX_N];
int d[MAX_N]; // 如果到顶点 i 的距离是 0x3f3f3f3f,则说明不存在源点到 i 的最短路
void spfa(int s) {
memset(inq, 0, sizeof(inq));
memset(d, 0x3f, sizeof(d));
d[s] = 0;
inq[s] = true;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (d[u] + e[i].w < d[v]) {
d[v] = d[u] + e[i].w;
if (!inq[v]) {
q.push(v);
inq[v] = true;
}
}
}
}
}
4、Bellman-Ford
概述
对于一个不存在负权回路的图,Bellman-Ford 算法求解最短路径的方法如下:
设其顶点数为 n,边数为 m。设其源点为 source,数组dist[i]记录从源点 source 到顶点 i 的最短路径,除了dist[source]初始化为 0 外,其它dist[]皆初始化为 MAX。以下操作循环执行 n-1 次:
对于每一条边 arc(u, v),如果 dist[u] + w(u, v) < dist[v],则使 dist[v] = dist[u] + w(u, v),其中 w(u, v) 为边 arc(u, v) 的权值。
n-1 次循环,Bellman-Ford 算法就是利用已经找到的最短路径去更新其它点的dist[]。
#include <iostream>
#include <stack>
using namespace std;
#define MAX 10000 // 假设权值最大不超过 10000
struct Edge
{
int u;
int v;
int w;
};
Edge edge[10000]; // 记录所有边
int dist[100]; // 源点到顶点 i 的最短距离
int path[100]; // 记录最短路的路径
int vertex_num; // 顶点数
int edge_num; // 边数
int source; // 源点
bool BellmanFord()
{
// 初始化
for (int i = 0; i < vertex_num; i++)
dist[i] = (i == source) ? 0 : MAX;
// n-1 次循环求最短路径
for (int i = 1; i <= vertex_num - 1; i++)
{
for (int j = 0; j < edge_num; j++)
{
if (dist[edge[j].v] > dist[edge[j].u] + edge[j].w)
{
dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
path[edge[j].v] = edge[j].u;
}
}
}
bool flag = true; // 标记是否有负权回路
// 第 n 次循环判断负权回路
for (int i = 0; i < edge_num; i++)
{
if (dist[edge[i].v] > dist[edge[i].u] + edge[i].w)
{
flag = false;
break;
}
}
return flag;
}
void Print()
{
for (int i = 0; i < vertex_num; i++)
{
if (i != source)
{
int p = i;
stack<int> s;
cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是: ";
while (source != p) // 路径顺序是逆向的,所以先保存到栈
{
s.push(p);
p = path[p];
}
cout << source;
while (!s.empty()) // 依次从栈中取出的才是正序路径
{
cout << "--" << s.top();
s.pop();
}
cout << " 最短路径长度是:" << dist[i] << endl;
}
}
}
int main()
{
cout << "请输入图的顶点数,边数,源点:";
cin >> vertex_num >> edge_num >> source;
cout << "请输入" << edge_num << "条边的信息:n";
for (int i = 0; i < edge_num; i++)
cin >> edge[i].u >> edge[i].v >> edge[i].w;
if (BellmanFord())
Print();
else
cout << "Sorry,it have negative circle!n";
return 0;
}
本文摘抄自计蒜客,欢迎加入计蒜客的大家庭,戳旁边这里https://passport.jisuanke.com/?invite=rkgqimi