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集合为空。
#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; }
#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; }
适用条件:能够判断负环,可以有负权边。
#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; }
优化思路:由于\(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; }