单源最短路常用模板
SPFA
朴素版
//Bellman-Ford 队列优化
//SPAF
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int n, m, s;
const int inf = 99999999;
cin >> n >> m >> s;
vector<int> a(m + 1), b(m + 1), c(m + 1), first(n + 1, -1), next(m + 1), dis(n + 1, inf);
vector<bool> book(n + 1, false);
queue<int> q;
dis[s] = 0;
for (int i = 1; i <= m; ++i)
{
cin >> a[i] >> b[i] >> c[i];
next[i] = first[a[i]];
first[a[i]] = i;
}
q.emplace(s);
book[s] = true;
while (!q.empty())
{
int k = first[q.front()];
while (k != -1)
{
if (dis[b[k]] > dis[a[k]] + c[k])
{
dis[b[k]] = dis[a[k]] + c[k];
if (book[b[k]] == false)
{
q.emplace(b[k]);
book[b[k]] = true;
}
}
k = next[k];
}
book[q.front()] = false;
q.pop();
}
for (int i = 1; i <= n; ++i)
cout << dis[i] << " ";
return 0;
}
SPFA + 链式前向星
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct EDGE
{
int to;
int next;
int w;
}edge[101];
int head[101], cnt = 1;
int n, m;
int dis[101];
bool vis[101];
const int inf = 99999;
queue<int> q;
void add(int a, int b, int w)
{
edge[cnt].w = w;
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void spfa(int x)
{
//初始化dis数组
fill(dis, dis + 101, inf);
//将起点放入队列用起点松弛
q.push(x);
dis[x] = 0;
vis[x] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
//松弛操作
for (int i = head[u]; i != 0; i = edge[i].next)
{
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].w) {
dis[v] = dis[u] + edge[i].w;
//如果松弛成功且这个点又没有再队列中就把它加入队列尾部
if (vis[v] == 0) {
q.push(v);
vis[v] = 1;
}
}
}
}
}
int main()
{
cin >> n >> m;
int a, b, c;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
cout << "输入访问点:";
int x; cin >> x;
spfa(x);
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
system("pause");
return 0;
}
Digkstra
Dijkstra + 链式前向星
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, A, B;
int dis[10001];
bool vis[10001];
const int inf = 999999999;
//链式前向星
struct EDGE
{
int w;
int to;
int next;
}edge[10001];
int head[10001];
int cnt = 1;
void add(int a, int b, int w)
{
edge[cnt].to = b;
edge[cnt].w = w;
edge[cnt].next = head[a];
head[a] = cnt++;
}
void Dijkstra(int node)
{
fill(dis, dis + 10001, inf);
dis[node] = 0;
for (int i = 1; i <= n - 1; i++)
{
int u = -1,minn = inf;
for (int j = 1; j <= n; j++)
{
if (vis[j] == false && dis[j] < minn)
{
u = j;
minn = dis[j];
}
}
if (u == -1)break;
vis[u] = 1;
for (int i =head[u]; i!= 0; i = edge[i].next)
{
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].w)
dis[v] = dis[u] + edge[i].w;
}
}
}
int main()
{
cin >> n >> A >> B;
fill(head, head + 10001, 0);
int x = 1;
while (x <= n)
{
int k, a;
cin >> k;
for (int i = 0; i < k; i++)
{
cin >> a;
if(i == 0)
add(x, a, 0);
else{
add(x, a, 1);
}
}
x++;
}
Dijkstra(A);
if (dis[B] < inf)
cout << dis[B] << endl;
else
cout << "-1" << endl;
system("pause");
return 0;
}
Dijkstra + 堆优化
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
const int N = 100010;
const int M = 500010;
// 堆优化版本 O((m + n)logn)
// 不能处理负边权
struct edge
{
int to, dis , next;
}e[M];
int head[N], dis[N], cnt, n , m ,s;
bool vis[N];
void add(int a,int b,int v)
{
cnt++;
e[cnt].dis = v;
e[cnt].to = b;
e[cnt].next = head[a];
head[a] = cnt;
}
struct node
{
int dis;
int pos;
bool operator <(const node &x)const{
return x.dis < dis;
}
};
priority_queue<node> q;
void dijkstra()
{
dis[s] = 0;
q.push((node){0,s});
while(!q.empty())
{
node tmp = q.top();
q.pop();
int x = tmp.pos;
if(vis[x])continue;
vis[x] = 1;
for(int i = head[x];i ;i = e[i].next)
{
int y = e[i].to;
if(dis[y] > dis[x] + e[i].dis)
{
dis[y] = dis[x] + e[i].dis;
if(!vis[y])
{
q.push((node){dis[y],y});
}
}
}
}
}
int main()
{
cin >> n >> m >> s;
for(int i = 1;i <= n ;i ++)dis[i] = 0x7fffffff;
for(register int i = 0;i < m ; ++i)
{
register int a , b , c;
scanf("%d %d %d",&a , &b ,&c);
add(a , b ,c);
}
dijkstra();
for(int i = 1;i <= n ;i ++)
{
printf("%d ", dis[i]);
}
return 0;
}
Bellman-ford 算法
//Bellman-Ford 普通算法
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, m, s;
cin >> n >> m >> s;
const int inf = 99999;
vector<int> a(m), b(m), c(m), dis(n, inf);
for (int i = 0; i < m; ++i)
cin >> a[i] >> b[i] >> c[i];
dis[s - 1] = 0;
//Bellman-Ford 算法核心内容
bool check;
for (int k = 0; k < n - 1; ++k)
{
check = false;
for (int i = 0; i < m; ++i)
if (dis[b[i] - 1] > dis[a[i] - 1] + c[i])
{
dis[b[i] - 1] = dis[a[i] - 1] + c[i];
check = true;
}
if (!check)
break;
}
//Bellman-Ford 算法也可用于判断图中是否含有负权回路
for (int i = 0; i < m; ++i)
if (dis[b[i] - 1] > dis[a[i] - 1] + c[i])
{
cout << "此图中含有负权回路" << endl;
break;
}
for (auto i : dis)
cout << i << " ";
return 0;
}
原文链接: https://www.cnblogs.com/wlw-x/p/12628246.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/339751
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!