[数据结构与算法-15]单源最短路径(Dijkstra+SPFA)

2023-08-01 20:43:10

单源最短路径

问题描述

分别求出从起点到其他所有点的最短路径，这次主要介绍两种算法，Dijkstra和SPFA。若无负权优先Dijkstra算法，存在负权选择SPFA算法。

Dijkstra算法

非负权
稳定

Dijkstra算法的解决方案

Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

Dijkstra算法的解题思想

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。

具体步骤

选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。
调整T中各顶点到源点v的最短路径。因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。
再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

P4779 【模板】单源最短路径（标准版)

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60 $；

$\text{Ag} \rightarrow \text{Cu}$ ;

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$ 。第二行起 mm 行，每行三个非负整数 $u_i$, $v_i$, $w_i$ ，表示从 u_iu**i 到 v_iv**i 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

输入输出样例

输入 #1复制
4 6 1

1 2 2

2 3 2

2 4 1

1 3 5

3 4 3

1 4 4
输出 #1复制
0 2 4 3
说明/提示

样例解释请参考数据随机的模板题。

$1 \leq n \leq 10^5$ ；

$1 \leq m \leq 2\times 10^5$ ；

$s = 1$ ；

$1 \leq u_i, v_i\leq n$ ；

$0 \leq w_i \leq 10 ^ 9$ ,

$0 \leq \sum w_i \leq 10 ^ 9$ 。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

// 预定义

#include <cstdio>

#include <queue>

#define MAXN 100000

#define MAXM 200000

#define IFN ((1<<31)-1)

int cnt, n, m, s, head[MAXN + 1], dis[MAXN + 1];

// 用vis[]记录是否已经找到最短路径

bool vis[MAXN + 1];

// 构造边

struct Edge {

	int to, dis, next;

}edge[MAXM + 1];

// 构造节点

struct node {

    // 当前节点以及当前节点的最短路径

	int pos, dis;

    // 重载运算符，使dis小的优先级更高

	inline bool operator < (const node& a)const {

		return dis > a.dis;

	}

};

// 创建有限队列

std::priority_queue<node> heap;

// 快读

inline int read() {

	int num = 0, f = 1; char ch = getchar();

	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }

	while (ch >= '0' && ch <= '9') { num = (num<<1) + (num<<3) + (ch^48);ch = getchar(); }

	return f * num;

}

// 链式向前星添加边

inline void add(int from, int to, int dis) {

	edge[++cnt].dis = dis;

	edge[cnt].to = to;

	edge[cnt].next = head[from];

	head[from] = cnt;

}

// Dijkstra求最短路径

void Dijkstra() {

	while (!heap.empty()) {

        // 获取当前距离起点最短的节点

		int cpos = heap.top().pos; heap.pop();

        // 若这个节点已经遍历过所有的边则pass

		if (vis[cpos]) continue;

		vis[cpos] = 1;

        // 遍历当前节点的所有边

		for (int i = head[cpos]; i; i = edge[i].next) {

			int to = edge[i].to;

            // 若发现到达下一个点的更短路径更新dis

			if (dis[to] > dis[cpos] + edge[i].dis) {

				dis[to] = dis[cpos] + edge[i].dis;

                // 队列中实时更新已经找到的路径

				heap.push(node({ to,dis[to] }));

			}

		}

	}

}

int main() {

	n = read(), m = read(), s = read();

    // 预处理

	for (int i = 0; i < MAXN + 1; i++) {

		dis[i] = IFN;

	}

	dis[s] = 0;

    heap.push(node({ s,0 }));

    // 存图

	for (int i = 1, u, v, w; i <= m; i++) {

		u = read(), v = read(), w = read();

		add(u, v, w);

	}

    // 求最短路径

	Dijkstra();

    // 输出

	for (int i = 1; i <= n; i++)

		printf("%d ", dis[i]);

	return 0;

}

SPFA算法

描述

SPFA（Shortest Path Faster Algorithm）算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。在 NOI2018Day1T1归程中正式被卡，其时间复杂度为O(nm)，远劣于Dijkstra的O((n+m)log m)。

SPFA算法的解题思想

我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。

P3371 【模板】单源最短路径（弱化版)

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 $n,m$ 分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$ 表示一条 $u \to v$ 的，长度为 $w$ 的边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$ 。

输入输出样例

输入 #1复制
4 6 1

1 2 2

2 3 2

2 4 1

1 3 5

3 4 3

1 4 4
输出 #1复制
0 2 4 3
说明/提示

【数据范围】

对于 $20\%$ 的数据：$1\le n \le 5$ ，$1\le m \le 15$ ；

对于 $40\%$ 的数据：$1\le n \le 100$ ，$1\le m \le 10^4$ ；

对于 $70\%$ 的数据：$1\le n \le 1000$ ，$1\le m \le 10^5$ ；

对于 $100\%$ 的数据：$1 \le n \le 10^4$ ，$1\le m \le 5\times 10^5$ ，保证数据随机。

对于真正 $100\%$ 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

完整解答

#include <cstdio>

#include <queue>

#define MAXN 10000

#define MAXM 500000

#define IFN (1<<31)-1

int cnt, n, m, s, head[MAXN+1], dis[MAXN+1], vis[MAXN+1];

struct Edge {

	int to, w, next;

}edge[MAXM+1];

// 快读

inline int read() {

	int num=0, f = 1;char ch = getchar();

	while (ch < '0' || ch > '9') { if (ch == '-')f = -1;ch = getchar(); }

	while (ch >= '0' && ch <= '9') { num = (num << 3) + (num << 1) + (ch ^ 48);ch = getchar(); }

	return num * f;

}

inline void add(int from, int to, int w) {

	edge[++cnt].w = w;

	edge[cnt].to = to;

	edge[cnt].next = head[from];

	head[from] = cnt;

}

std::queue<int> q;

void SPFA() {

    // 开始节点进队列

	q.push(s);

	while (!q.empty()) {

        // 获取当前节点，出队列时取消标记

		int cpos = q.front(); q.pop();vis[cpos] = 0;

		for (int i = head[cpos]; i; i = edge[i].next) {

			int to = edge[i].to;

            // 若可优化才进队列

			if (dis[to] > dis[cpos] + edge[i].w) {

				dis[to] = dis[cpos] + edge[i].w;

                // 进队列加标记

				if (!vis[to]) {q.push(to);vis[to] = 1;}

			}

            // 不可优化直接出队，当队列为空时无可优化节点

		}

	}

}

int main() {

	n = read(), m = read(), s = read();

	for (int i = 0; i < MAXN + 1; i++) {

		dis[i] = IFN;

	}

	dis[s] = 0;

	for (int i = 1,u,v,w; i <= m; i++) {

		u = read(), v = read(), w = read();

		add(u, v, w);

	}

	SPFA();

	for (int i = 1; i <= n; i++) {

		printf("%d ", dis[i]);

	}

	return 0;

}

码农公寓

单源最短路径

问题描述

Dijkstra算法

Dijkstra算法的解决方案

Dijkstra算法的解题思想

具体步骤

P4779 【模板】单源最短路径（标准版)

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示