最短路

Floyd

多源最短路
首先，最暴力的做法，三个for，如果i到j的距离大于i到k再到j的距离，也就是dis[i][j] > dis[i][k] + dis[k][j] 那么就更新dis[i][j]的值,复杂度O(n³)，没什么用。

#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(n²)，经过堆优化能到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