最短路
程序员文章站
2022-06-19 09:23:42
Floyd多源最短路首先，最暴力的做法，三个for，如果i到j的距离大于i到k再到j的距离，也就是dis[i][j] > dis[i][k] + dis[k][j] 那么就更新dis[i][j]的值,复杂度O(n3)，没什么用。#include //万能头文件 /*多源最短路 Floyd算法*/using namespace std;ll edge[100][100];//邻接矩阵edge[i][j]表示...
Floyd
多源最短路
首先，最暴力的做法，三个for，如果i到j的距离大于i到k再到j的距离，也就是dis[i][j] > dis[i][k] + dis[k][j] 那么就更新dis[i][j]的值,复杂度O(n3)，没什么用。
#include<bits/stdc++.h> //万能头文件 /*多源最短路 Floyd算法*/
using namespace std;
ll edge[100][100]; //邻接矩阵 edge[i][j]表示i到j最短距离
int main(){
int n,m;
cin>>n>>m; //n定点数,m路径数
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){ //预处理
edge[i][j]=1e9; //没有路径值为1e9;
}
edge[i][i]=0;
}
while(m--){
int u,v,w;
cin>>u>>v>>w;
edge[u][v]=edge[v][u]=w; //无向图;
}
for(int k = 1; k <= n; k++){ //以顶点k松弛 i->k->j;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
//i->k,k->j有路径且路径长度小于i->j 更新值;
if(edge[i][k]!=1e9 && edge[k][j]!=1e9 && edge[i][j]>edge[i][k]+edge[k][j]){
edge[i][j]=edge[i][k]+edge[k][j];
}
}
}
}
while(1){ //测试u->v的最短路径;
int u,v;
cin>>u>>v;
cout<<edge[u][v]<<endl;
}
return 0;
}
Bellman-ford
Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行持续地松弛，每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出外循环。Bellman-ford算法浪费了许多时间做没有必要的松弛。
#include<bits/stdc++.h> //万能头文件 //可解决负权值的图,并判断是否有负环(负权回路): /*单源最短路 Bellman-Ford算法*/
using namespace std;
int u[100],v[100],w[100],dst[100]; //u起点,v终点,w权值, dst[i]表示从源点到i点的最短路径;
int main(){
int n,m; //n个点,m条路;
cin>>n>>m;
for(int i = 1; i <= m; i++)
cin>>u[i]>>v[i]>>w[i];
int s,t; //求s->t的最短路径;
while(cin>>s>>t){
for(int i = 1; i <= n; i++)
dst[i]=1e9;
dst[s]=0;
for(int i = 1; i <= n-1; i++){ //正权图最多更新n-1次
int flag=1; //记录本次有无松弛操作;
for(int j = 1; j <= m; j++){
if(dst[v[j]]>dst[u[j]]+w[j]){
dst[v[j]]=dst[u[j]]+w[j]; //松弛;
flag=0;
}
}
if(flag) break; //优化(没有松弛直接退出循环);
}
int flag=1;
for(int i = 1; i <= m; i++){
if(dst[v[i]]>dst[u[i]]+w[i]){ //if还能松弛,有负环;
flag=0;
break;
}
}
if(flag)
cout<<dst[t]<<endl;
else
cout<<"have negative circle"<<endl;
}
return 0;
}
一般解题也用不到。。。
迪杰斯特拉(Dijkstra)
dij算法体现贪心的思想，每次找一个与起点最近的点，对这个点连接的边进行松弛，本身复杂度O(n2)，经过堆优化能到O(nlogn)，直接起飞。
但不能解决负权图。
直接放堆优化代码。
链式前向星存图
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
int to; //该边指向的点
int next; //以u为起点的上一条边的编号
int w; //权值
}e[200005];
struct node{
int w;
int index;
bool operator<(const node &a) const{
return w>a.w; //运算符重载
}
}p;
int cnt = 0; //边的编号
int head[100005];
int vis[100005]={0};
ll dis[100005];
int n,m,s;
void add(int u, int v, int w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u]; //以u为起点的上一条边的编号;
head[u] = cnt++; //以u为起点的最后一条边的编号;
}
void dij(){
for(int i = 0; i <= n; i ++)
dis[i] = 1e9;
dis[s] = 0;
priority_queue<node> q;
q.push({0,s});
while(!q.empty()){
int u = q.top().index;
int d = q.top().w;
q.pop();
if(dis[u]<d) continue;
for(int i = head[u]; i != -1; i = e[i].next){
int v = e[i].to;
if(dis[v] > e[i].w + dis[u]){
dis[v] = e[i].w + dis[u];
q.push({dis[v], v});
}
}
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d %d %d", &n, &m, &s);
for(int i = 0; i < m; i ++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
// add(v,u,w);
}
dij();
for(int i = 1; i <= n; i ++){
if(i > 1) printf(" ");
printf("%d", dis[i]);
}
return 0;
}
vector存图
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
int to,w;
};
vector<edge> g[100005];
int dst[100005]={0};
int main(){
int n,m,s;
cin>>n>>m>>s;
while(m--){
int u,v,w;
cin>>u>>v>>w;
g[u].push_back({v,w});
}
priority_queue<pair<int,int>, vector<pair<int,int> > ,greater<pair<int,int> > > q;
for(int i = 1; i <= n; i++)
dst[i]=1e9;
dst[s]=0;
q.push({0,s});
while(!q.empty()){
pair<int,int> p=q.top();
q.pop();
int u = p.second;
int d = p.first;
if(dst[u]<d) continue;
for(int i = 0; i < g[u].size(); i++){
edge e = g[u][i];
if(dst[e.to]>d+e.w){
dst[e.to]=d+e.w;
q.push({dst[e.to],e.to});
}
}
}
for(int i = 1; i <= n; i++){
if(i>1) cout<<" ";
cout<<dst[i];
}
cout<<endl;
return 0;
}
本文地址：https://blog.csdn.net/HHeyanjie/article/details/107589423