最短路算法合集

本文主要是介绍最短路算法合集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

dijkstra算法

思路：

1、将所有顶点分为p、q两个集合，p已求出最短路径，q未求出最短路径。

2、令源点\(start\)到自己的距离为0，即\(dis[start]=0;\)

3、从p集合中找到距离源点最近的点，与之有边\(<u,v,w>\)相连的点v到源点的距离可更新为\(dis[v]=min(dis[v],dis[u]+w)\)，不断重复直到q集合为空。

朴素版 O( \(n^2\) )：

#include<bits/stdc++.h>
using namespace std;
const int N = 510, M=1e5+10,INF = 0x3f3f3f3f;
int dis[N], vis[N],h[N],to[M],w[M],ne[M],idx;
int n, m, start;
void add(int u,int v,int c) {
	to[++idx]=v;
	w[idx]=c;
	ne[idx]=h[u];
	h[u]=idx;
}
void dijkstra() {
	memset(dis,0x3f,sizeof dis);
	dis[start] = 0;  //起点距离为0
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++)//在还未确定最短路的点中，找到距离最小的点
			if (!vis[j] && (t == -1 || dis[j] < dis[t]))
				t = j;
		vis[t] = 1;
		for (int j = h[t]; j != -1; j=ne[j]) { //用t更新其他点的距离
			int k=to[j];
			dis[k] = min(dis[k], dis[t] + w[j]);
		}
	}
}
int main() {
	cin >> n >> m ;
	memset(h,-1,sizeof h); //初始化h数组
	int x, y, z;
	for (int i = 1; i <= m; i++) { //输入边
		cin >> x >> y >> z;
		add(x,y,z);
	}
	start = 1;
	dijkstra();
	if (dis[n] == INF)
		cout << -1;
	else
		cout << dis[n];
	return 0;
}

堆优化版O(\(m\ log_n\))：

优化思路：时间开销主要在查找距离p集合最近的点，可以使用优先队列进行优化。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5, M = N * 2;
int n, m, s;
int h[N], to[M], w[M], ne[M], idx;
int dis[N];
bool vis[N];
void add(int u, int v, int c) { //链式前向星加边
	to[++idx] = v;
	w[idx] = c;
	ne[idx] = h[u];
	h[u] = idx;
}

void dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > heap; //优先队列（小根堆）
	heap.push({0, s}); //把起点放入堆中
	while (heap.size()) { //遍历堆
		int t = heap.top().second; //取出堆顶元素，进行更新
		heap.pop();
		if (vis[t]) continue;
		vis[t] = true;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = to[i];
			if (dis[j] > dis[t] + w[i]) { //更新，松弛操作
				dis[j] = dis[t] + w[i];
				heap.push({dis[j], j});
			}
		}
	}

}

int main() {
	memset(h, -1, sizeof h);
	cin >> n >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	s=1; //起点是1
	dijkstra();
	if (dis[n] == 0x3f3f3f3f)
		cout << -1;
	else
		cout << dis[n];
	return 0;
}

补充：

建反向图：

1、反向图1

2、反向图2

Bellman_ford

思路：以每条边来松弛，如果发现终点能够通过该边使得路径变短，那么更新。

判断负环：在没有负环的图中，每个点最多被其他\(n-1\)个点各更新一次，如果被更新了第\(n\)次那么说明有负环。

复杂度\(O(nm)\)

适用条件：能够判断负环，可以有负权边。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+10;
int n,m;
int dis[maxn];
vector<pii>edge[150];
void in() {
	int a,b,c;
	for(int i=1; i<=m; i++) {
		cin>>a>>b>>c;
		edge[a].push_back(make_pair(b,c));
		edge[b].push_back(make_pair(a,c));
	}
}
void Bellman_ford(int st) {
	dis[st]=0;
	for(int k=1; k<n; k++) { //对应n-1伦操作
		bool flag=1;
		for(int i=1; i<=n; i++) {
			for(int j=0; j<edge[i].size(); j++) {
				int u=i,v=edge[i][j].first,w=edge[i][j].second;
				if(dis[v]>dis[u]+w) {
					dis[v]=dis[u]+w;
					flag=0;
				}
			}
		}
		if(flag)break;
	}
	for(int i=1; i<=n; i++) {
		for(int j=0; j<edge[i].size(); j++) {
			int u=i,v=edge[i][j].first,w=edge[i][j].second;
			if(dis[v]>dis[u]+w) {
				cout<<"fuhuan"; 
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	while(cin>>n>>m&&(n||m)) {
		for(int i=1; i<=n; i++)edge[i].clear(),dis[i]=INF;
		in();
		Bellman_ford(1);
		cout<<dis[n]<<endl;
	}
	return 0;
}

SPFA（优化版Bellman_ford）

优化思路：由于\(Bellman_ford\)的核心在于松弛操作，易得只有起点被更新了，才能够更新与它相连的点，只需使用队列记录能够更新其他点的点即可。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+10;
int n,m;
int dis[maxn];
bool vis[maxn];
int times[maxn];
vector<pii>edge[150];
int read() {
	int s=0,t=1;
	char c=getchar();
	while(!isdigit(c)) {
		if(c=='-')t*=-1;
		c=getchar();
	}
	while(isdigit(c)) {
		s=(s<<3)+(s<<1)+c-48;
		c=getchar();
	}
	return s*t;
}
void in() {
	int a,b,c;
	for(int i=1; i<=m; i++) {
		a=read();
		b=read();
		c=read();
		edge[a].push_back(make_pair(b,c));
		edge[b].push_back(make_pair(a,c));
	}
}
void SPFA(int st) {
	queue<int>q;
	vis[st]=1;
	q.push(st);
	dis[st]=0;
	while(q.size()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0; i<edge[u].size(); i++) {
			int v=edge[u][i].first,w=edge[u][i].second;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				if(!vis[v]) {
					q.push(v);
					vis[v]=1;
					times[v]++;
					if(times[v]==n)return ;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	while(1) {
		n=read();
		m=read();
		if(n==m&&!n)break;
		for(int i=1; i<=n; i++)edge[i].clear(),dis[i]=INF;
		in();
		SPFA(1);
		cout<<dis[n]<<endl;
	}
	return 0;
}

这篇关于最短路算法合集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！