chail's Blog
博客 分类 标签
chail's Blog

目录

目录

最短路算法：Dijkstra&Bellman-Ford&SPFA

 收录于  类别 算法足迹
     约 2311 字   预计阅读 11 分钟 

最短路算法：Dijkstra&Bellman-Ford&SPFA

书接上回，继续图论中的经典算法，今天是最短路的经典算法：Dijkstra，Bellman--Ford，以及Bellman--Ford的优化版本SPFA。

如图，求最短路径。

顶点数n 边数m,n<=10,m<=100

m条边的顶点和权值

终点

顶点0到终点的最短路径

6 9
0 2 5
0 3 30
1 0 2
1 4 8
2 1 15
2 5 7
4 3 4
5 3 10
5 4 18
4
28

我们需要找到0到某个点的最短路径。等等，最短？和上次的最小生成树很像啊。不过并不完全一样。虽然同样都是找最小的权值，但是最小生成树要求的是连通所有节点，路径并非是最短的，而最短路问题要求找到权值最短的路径。

Dijkstra的思想和最小生成树的Prim比较相似。同样把注意力放在节点上：我们从起点出发，选择起点可去的那条最短的路，以此到达了下一个点，那么不难想到，这条路径就是从起点到下一个点的最短路径（事实上应该有一个严格的证明，不过这里问题不在这）。

**那么以此类推，每次都选择当前能走的最短的路，以此到达的点就是起点到这个点的最短路。**这简直和Prim一模一样对吧！不过在这里是一种递推关系，我们通过一步步求解最短的找到目标的最短路。

还是一样，写一个结构体，构造一个邻接表来构建图。思考一下，怎么样每次都找到可走的最短的路。直接枚举太慢了，显然不符合我们的风度。同样采用Prim中的优先队列优化方法，把能走的路存入优先队列，这样每次都能找到最短的。再用一个数组dijk来记录最短路，$dijk[i]表示到达点的最短路。设当前选择的路的长度为表示到达i点的最短路。设当前选择的路的长度为l，当前将从，当前将从i到到j，那么可以得到递推式，那么可以得到递推式dijk[j] = dijk[i] + l$。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct r{
	int f;
	int t;
	int l;
	bool operator<(const r& oth) const{
		return l>oth.l;
	}
};
int dijk[15];
bool ud[15] = {false};
vector<r> rs[15];
priority_queue<r> q;
int main(){
	int n, m, to;
	cin >> n >> m;
	for(int i=1;i<=m;++i){
		int a, b, l;
		cin >> a >> b >> l;
		rs[a].push_back({a,b,l});
	}
	cin >> to;
	q.push({0, 0, 0});
	dijk[0] = 0;
	while(!q.empty()){
		r cr = q.top();
		q.pop();
		if(ud[cr.t]) continue;
		dijk[cr.t] = cr.l;
		ud[cr.t] = true;
		if(!rs[cr.t].empty()){
			for(r tr:rs[cr.t]){
				if(!ud[tr.t]) {
					tr.l += dijk[tr.f];//最短路径的值 
					q.push(tr);
				}
			}
		}
	}
	cout << dijk[to];
	return 0;
}

平面上有$n$个点$（n≤100）$，每个点的坐标均在$-10000~10000$之间。其中的一些点之间有连线。

若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

已知两点坐标分别为 $（x1,y1) (x2,y2)$, 则 两点间的距离为 $sqrt( (x2-x1)* (x2-x1) + (y2-y1)*(y2-y1) )$

共$n+m+3$行，其中:

第一行为整数$n$。

第2行到第$n+1$行（共$n$行） ，每行两个整数$x$和$y$，描述了一个点的坐标。

第$n+2$行为一个整数$m$，表示图中连线的个数。

此后的$m$ 行，每行描述一条连线，由两个整数$i$和$j$组成， 表示第$i$个点和第$j$个点之间有连线。

最后一行：两个整数$s$和$t$，分别表示源点和目标点。

一行，一个实数（保留两位小数），表示从$s$到$t$的最短路径长度。

5 
0 0
2 0
2 2
0 2
3 1
5 
1 2
1 3
1 4
2 5
3 5
1 5
3.41

事实上，Dijkstra会出点问题：如果存在负权的边，那么Dijkstra就会失效，因为它的贪心策略只注重当下，没有考虑到后面可能的负边。

而Bellman--Ford算法可以解决这个问题。Bellford--Ford通过松弛来一步步找到到达终点的最短路。

用一个$dis$数组来记录到$i$的最短路，初始化为最大值。将起点的$dis$初始化为0。不断地遍历已知的路来更新最短路。当遍历了$n-1$遍时，就找到了所有的最短路。

怎么解释呢，比如第一次遍历时更新了从起点到相邻点的$dis$，第二次更新了相邻点的相邻点，也可能包括起点，以此类推…最终所有点的$dis$都得到了更新，也就得到了最短路。这实在是一种有趣的动态规划的方法。

用结构体存储边，按思路遍历$n-1$次边即可。不过这显然浪费了性能，因为一开始后面的点根本去不了，而到了后面前面的点或许已经找到了最短路，有时所有点都找到了最优解但仍然在遍历。

有一个简单的优化方案，我们可以用一个变量来记录每次遍历是否有点的情况发生了改变。如果有一次遍历没有任何$dis$改变，那么此时已经找到了最优解，结束遍历。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;
struct p{
	double x;
	double y;
};
struct l{
	int f;
	int t;
	double len;
};
vector<l> ls;
p ps[105];
double dis[105];
int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;++i){
		double a, b;
		cin >> a >> b;
		ps[i].x=a;
		ps[i].y=b;
	}
	int m;
	cin >> m;
	for(int i=1;i<=m;++i){
		int x, y;
		cin >> x >> y;
		double len = sqrt((ps[x].x-ps[y].x)*(ps[x].x-ps[y].x)+(ps[x].y-ps[y].y)*(ps[x].y-ps[y].y));
		ls.push_back({x, y, len});
	}
	int s, t;
	cin >> s >> t;
	fill(dis, dis+1+n, 9999999);
	dis[s] = 0;
	for(int k=1;k<n;++k){
		bool flag = false;
		for(l pl:ls){
			if(dis[pl.t]>dis[pl.f]+pl.len){
				dis[pl.t] = dis[pl.f]+pl.len;
				flag = true;
			}
		}
		if(!flag) break;
	}
	cout << fixed << setprecision(2) << dis[t];
	return 0;
}

显然这样只解决了一部分问题，“一开始后面的点根本去不了，而到了后面前面的点或许已经找到了最短路”的问题还没有得到解决，对此还有一个优化方案，那就是只松弛能被松弛的两个点。这就是Bellman-Ford的进化版：SPFA。

用邻接表存储图，用一个队列来存储当前还没有得到答案并能松弛的点。一开始把起点推入队列，然后不断地取出队列里的点，遍历该点的边并更新dis。对于更新了的点，还可以继续通过它找到答案，所以接下来把它推入队列。就这样循环往复，最后便高效地得到了答案。

#include <iostream>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
struct p{
	int x;
	int y;
};
struct l{
	int t;
	double len;
};
vector<l> ls[105];
p ps[105];
double dis[105];
queue<int> q;
bool inq[105] {false};
int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;++i) cin >> ps[i].x >> ps[i].y;
	int m;
	cin >> m;
	for(int i=1;i<=m;++i){
		int x, y;
		cin >> x >> y;
		double len = sqrt((ps[x].x-ps[y].x)*(ps[x].x-ps[y].x)+(ps[x].y-ps[y].y)*(ps[x].y-ps[y].y));
		ls[x].push_back({y, len});
	}
	fill(dis, dis+1+n, 9999999);
	int s, t;
	cin >> s >> t;
	dis[s] = 0;
	q.push(s);
	inq[s] = true;
	while(!q.empty()){
		int f = q.front();
		q.pop();
		inq[f] = false;
		if(!ls[f].empty()){
			for(l cl:ls[f]){
				if(dis[cl.t]>dis[f]+cl.len){
					dis[cl.t] = dis[f]+cl.len;
					if(!inq[cl.t]) q.push(cl.t);
				}
			}
		}
	}
	cout << fixed << setprecision(2) << dis[t];
	return 0;
}
更新于 2026-01-27
 | 主页