手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

最短路算法报告On2021.6.8

时间:2021/6/8 21:07:01|来源:|点击: 次

离散数学最短路算法报告

P r o b l e m s Problems Problems

洛谷P1807 F l o y d Floyd Floyd

数据比较小允许 F l o y d Floyd Floyd
在这里插入图片描述

dp算法:

设计状态:
F [ x ] [ i ] [ j ] F[x][i][j] F[x][i][j]表示从i到j经过至多x个中间点的最短路径
状态转移:
F [ x ] [ i ] [ j ] = m i n { F [ x − 1 ] [ i ] [ j ] , F [ x − 1 ] [ i ] [ k ] + F [ x − 1 ] [ k ] [ j ] , ∀ k ∈ [ 1 , x ] } F[x][i][j]=min\{ F[x-1][i][j],F[x-1][i][k]+F[x-1][k][j],\forall k\in[1,x]\} F[x][i][j]=min{F[x1][i][j],F[x1][i][k]+F[x1][k][j],k[1,x]}
边界条件:
F [ 0 ] [ i ] [ j ] = { 0 , i = = j 无 穷 大 , i ! = j 并 且 i 和 j 不 连 通 < i , j > 长 度 , i , j 连 通 F[0][i][j]=\begin{cases}0,i==j\\无穷大,i!=j并且i和j不连通\\<i,j>长度,i,j连通\end{cases} F[0][i][j]=0,i==j,i!=jij<i,j>,i,j

空间优化:

使用滚动数组可以把状态的第一维给他扬了
此时状态转移方程为:
d i s t [ i ] [ j ] = m i n { d i s t [ i ] [ j ] , F [ i ] [ k ] + F [ k ] [ j ] , ∀ k ∈ [ 1 , n ] 且 < i , k > < k , j > 都 存 在 } dist[i][j]=min\{ dist[i][j],F[i][k]+F[k][j],\forall k\in[1,n]且<i,k><k,j>都存在\} dist[i][j]=min{dist[i][j],F[i][k]+F[k][j],k[1,n]<i,k><k,j>}

[P1807]最长路代码

注意与最短路的区别,平行边应该保留更长边(最短路时保留最短边)
初始化不直接联通的边权应为负无限大(最短路时为正无穷大)
状态转移时需要先判断经过 < i , x > < x , j > <i,x><x,j> <i,x><x,j>是否直接联通

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4;
int dist[maxn][maxn];
const int INF=-1e9;//
int n,m;
void init(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)dist[i][j]=0;
			else dist[i][j]=INF;
		}
	}
}
void add(int u,int v,int w){
	dist[u][v]=max(dist[u][v],w);
}

void Floyd(){
	for(int x=1;x<=n;x++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dist[i][x]!=INF&&dist[x][j]!=INF){//判断是否联通
					dist[i][j]=max(dist[i][j],dist[i][x]+dist[x][j]);//联通则更新最长路
				}
			}
		}
	}
}
int u,v,w;
int main(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w; 
		add(u,v,w);
	}
	Floyd();
	if(dist[1][n]>0)cout<<dist[1][n];
	else cout<<-1;
	return 0;
}

提交记录:

在这里插入图片描述

洛谷P3371 B e l l m a n − F o r d Bellman-Ford BellmanFord

数据较大, F l o y d Floyd Floyd没法存图, S P F A SPFA SPFA概率通过
在这里插入图片描述

松弛算法:

在这里插入图片描述

			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				只要v顶点被松弛了,那么就有可能以v为跳板松弛其他顶点
			}

每次松弛必定有至少一个顶点到原点的最短路径可以被固定,
那么每个顶点最多松弛 n − 1 n-1 n1次,所有的顶点都可以且应该被固定
如果还能继续松弛则原图上有负环

D i j k s t r a Dijkstra Dijkstra算法的区别:

都是松弛算法:
d i j k s t r a dijkstra dijkstra每次确定一个最短距离点,并用这个点去更新其他与之相连的边.
b e l l m a n f o r d bellman_ford bellmanford是每次更新所有的边,包括但不限于最短距离点到与之相连边,那么每次也都是可以产生最短距离点但是不知道是哪一个
如果存在边权为负,最短距离点可能会再次更新,
如果存在负环,则转转不已
d i j k s t r a dijkstra dijkstra一旦确定最短距离点就不会再更改

队列优化 S P F A SPFA SPFA

S h o r t e s t   P a t h   F a s t e r   A l g o r i t h m Shortest \ Path\ Faster \ Algorithm Shortest Path Faster Algorithm

核心算法:

while(!q.empty()){
		u=q.front();
		q.pop();
		inQueue[u]=false;
		for(int i=head[u];i;i=edges[i].next){
			v=edges[i].v;
			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				if(inQueue[v]==false){
					inQueue[v]=true;
					q.push(v);
				}
			}
		}
	}

非常像 B F S BFS BFS但是又有所区别:
B F S BFS BFS中每个顶点只能被拓展一次,也就是第一次搜索到它时
但是 S P F A SPFA SPFA中每个顶点有多次进入队列的机会

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
const int INF=2147483647;
int m,n,s;
int dist[maxn];
struct Edge{
	int u,v,w,next;
}edges[maxn];
int head[maxn];
int cnt_edges;
void add(int u,int v,int w){
	++cnt_edges;
	edges[cnt_edges].u=u;
	edges[cnt_edges].v=v;
	edges[cnt_edges].w=w;
	edges[cnt_edges].next=head[u];
	head[u]=cnt_edges;
}
bool inQueue[maxn];
queue<int> q;
void init(){
	while(!q.empty())q.pop();
	cnt_edges=0;
	for(int i=1;i<=n;i++){
		dist[i]=INF;
		head[i]=inQueue[i] =0;
		
	}
}
void SPFA(int S){
	dist[S]=0;
	q.push(S);
	inQueue[S]=true;
	int u,v,w;
	while(!q.empty()){
		u=q.front();
		q.pop();
		inQueue[u]=false;
		for(int i=head[u];i;i=edges[i].next){
			v=edges[i].v;
			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				if(inQueue[v]==false){
					inQueue[v]=true;
					q.push(v);
				}
			}
		}
	}
}
int u,v,w;
int main(){
	cin>>n>>m>>s;
	init();
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	SPFA(s);
	for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
	return 0;
}

提交记录

在这里插入图片描述

洛谷P4779 D i j k s t r a Dijkstra Dijkstra

会卡我的 S P F A SPFA SPFA,堆优化的 D i j k s t r a Dijkstra Dijkstra可以过
在这里插入图片描述

松弛算法:

所谓松弛算法:
选取当前节点 u u u到起点 S S S最近并且没有拓展过的点,遍历的所有后驱,如果发现起点 S S S到后驱 v v v的距离,要小于 S S S u u u的距离 + < u , v > +<u,v> +<u,v>的距离,则更新 v v v的距离为更短的距离,这个更新带来的后果是v的所有后驱节点有可能跟着 v v v沾光,也存在被松弛的可能,但是如果 v v v不能松弛,也就是 d i s ( S , v ) < d i s ( S , u ) + d i s < u , v > dis(S,v)<dis(S,u)+dis<u,v> dis(S,v)<dis(S,u)+dis<u,v>则v的后驱节点一定也没法沾 v v v的光

			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				heap.push(Node(v,dist[v]));
			}

堆优化:

如果不优化,那么每次寻找距离原点最近的并且没有被拓展过的点需要遍历一遍所有的顶点,
每次能够拓展出一个顶点,那么n个顶点需要拓展n次,每个顶点的后继顶点又有若干,那么总时间复杂度为 O ( n 2 + e ) O(n^2+e) O(n2+e)
使用优先队列priority_queue<Node> heap;
原来顶点没有专门的结构,现在用 N o d e Node Node结构体表示顶点的目的是:将顶点编号 u u u和到起点 S S S的距离 d d d捆绑(相当于 p a i r < i n t , i n t > pair<int,int> pair<int,int>,使得堆在按照第二关键字对 N o d e Node Node排序时,编号能够跟随距离一起排序),这就要求 N o d e Node Node类重载以下偏序运算符小于号(因为堆的排序规则是严格由小于号规定的)

将顶点按照距离起点 S S S的距离升序排列,这就保证了,从优先队列头上开始一个一个取出的顶点一定是"到 S S S最近"的顶点 u u u,但是不能保证 u u u是"没有拓展过的"顶点,可以开一个 v i s i t e d [ m a x n ] visited[maxn] visited[maxn]数组标记 u u u有没有拓展过
如此一来,"寻找距离原点最近的并且没有被拓展过的点"这一步可以由堆快速完成,堆的排序复杂度为O(logn),n个顶点入堆,总排序时间为O(nlogn),每次拿出一个顶点遍历它的所有后驱,所有的顶点都这样做一遍,恰好每条边遍历了一次且仅一次O(e),那么总时间复杂度降为 O ( n l o g n + e ) O(nlogn+e) O(nlogn+e)

完整代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3*1e7;
const int INF=1e9;
int n,m,s;
struct Edge{
	int u,v,w,next;
}edges[maxn];
int head[maxn];
int cnt_edges;
void add(int u,int v,int w){
	++cnt_edges;
	edges[cnt_edges].u=u;
	edges[cnt_edges].v=v;
	edges[cnt_edges].w=w;
	edges[cnt_edges].next=head[u];
	head[u]=cnt_edges;	
}
struct Node{
	int u;
	int d;
	Node(int _u=0,int _d=0):u(_u),d(_d){}
	bool operator<(const Node &node)const{//重载<运算符
		return node.d<d;
	}
};
int dist[maxn];
priority_queue<Node> heap;
bool visited[maxn];
void init(){
	while(!heap.empty())heap.pop();
	cnt_edges=0;
	for(int i=1;i<=n;i++){
		dist[i]=INF;
		head[i]=visited[i]=0;
	}
}

void Dijkstra(int S){
	dist[S]=0;
	Node temp(S,0);
	heap.push(temp);
	int u,v,w,d;
	while(!heap.empty()){
		temp=heap.top();
		heap.pop();
		u=temp.u;
		if(visited[u])continue;
		visited[u]=true;
		for(int i=head[u];i;i=edges[i].next){
			v=edges[i].v;
			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				heap.push(Node(v,dist[v]));
			}
		}
	}	
}
int main(){
	cin>>n>>m>>s;
	init(); 
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
	return 0;
}

提交记录:

在这里插入图片描述

最短路算法的应用:

洛谷P3385 S P F A SPFA SPFA判断负环

如果某个顶点被松弛了 n n n次及以上则一定存在负环
注意"被松弛的次数"是指一个顶点 v v v进入队列的总次数,不是指 d i s t [ v ] dist[v] dist[v]被更新的次数
因为每次从某个顶点出发,虽然可以"松弛"很多点,但是其中只有一个是可以固定下来有最短路的,也就是说每个顶点可能被多个前驱进行多次无效的"松弛"

			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				if(!inQueue[v]){
					//"松弛次数"指进入该语句块的次数,也就是有效松弛数
					++cnt_relaxed[v];
					if(cnt_relaxed[v]>n-1)return true;
					inQueue[v]=true;
					q.push(v);
				}
			}

完整代码

#include <bits/stdc++.h>
using namespace std;
int n,m,T;
const int INF=1e9;
const int maxn=1e6;
struct Edge{
	int u,v,w,next;
}edges[maxn];
int head[maxn];
int cnt_edges;
void add(int u,int v,int w){
	++cnt_edges;
	edges[cnt_edges].u=u;
	edges[cnt_edges].v=v;
	edges[cnt_edges].w=w;
	edges[cnt_edges].next=head[u];
	head[u]=cnt_edges;
}
int cnt_relaxed[maxn];
int dist[maxn];
bool inQueue[maxn];
queue<int> q;
void init(){
	while(!q.empty())q.pop();
	cnt_edges=0;
	for(int i=1;i<=n;i++){
		dist[i]=INF;
		inQueue[i]=head[i]=cnt_relaxed[i]=0;
	}
}

bool SPFA(int S){
	dist[S]=0;
	inQueue[S]=true;
	q.push(S);
	int u,v,w;
	
	while(!q.empty()){
		u=q.front();
		q.pop();
		inQueue[u]=false;
		for(int i=head[u];i;i=edges[i].next){
			v=edges[i].v;
			if(dist[v]>dist[u]+edges[i].w){
				
				
				dist[v]=dist[u]+edges[i].w;
				if(!inQueue[v]){
					++cnt_relaxed[v];
					if(cnt_relaxed[v]>n-1)return true;
					inQueue[v]=true;
					q.push(v);
				}
			}
			
		}
	}
	return false;
}

int u,v,w;
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		init();
		for(int i=1;i<=m;i++){
			cin>>u>>v>>w;
			add(u,v,w);
			if(w>=0)add(v,u,w);
		}
		if(SPFA(1))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	
	
	return 0;
}

提交记录

在这里插入图片描述

洛谷P1144 D i j k s t r a Dijkstra Dijkstra统计最短路数量

核心算法

如果发现更短的路则先前记录的最短路数量作废,如果发现新的同样长的最短路则最短路数量累加

			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				q.push(Node(v,dist[v]));
				cnt_path[v]=cnt_path[u]%mod;
			}
			else if(dist[v]==dist[u]+edges[i].w){
				cnt_path[v]=(cnt_path[v]+cnt_path[u])%mod;
			}

完整代码:

#include <bits/stdc++.h>
using namespace std;
const long long maxn=1e7;
const long long INF=1e9;
const long long mod=100003;
long long cnt_path[maxn];
long long dist[maxn];
long long N,M;
struct Edge{
	long long u,v,w,next;
}edges[maxn];
long long head[maxn];
long long cnt_edges;
void add(long long u,long long v,long long w){
	//此处原本想去除平行边,但是平行边也会对最短路数量产生贡献,因此必须保留
//	for(int i=head[u];i;i=edges[i].next){
//		if(edges[i].v==v){
//			edges[i].w=min(edges[i].w,w);
//			return;
//		}
//	}
	++cnt_edges;
	edges[cnt_edges].u=u;
	edges[cnt_edges].v=v;
	edges[cnt_edges].w=w;
	edges[cnt_edges].next=head[u];
	head[u]=cnt_edges;
	
}
struct Node{
	long long u,d;
	Node(long long _u=0,long long _d=0) :u(_u),d(_d){}
	bool operator<(const Node &node)const{
		return node.d<d;
	}
};

bool visited[maxn];
priority_queue<Node> q;

void init(){
	while(!q.empty())q.pop();
	cnt_edges=0;
	for(long long i=1;i<=N;i++){
		dist[i]=INF;
		cnt_path[i]=head[i]=visited[i]=0;
	}
	
}

void Dijkstra(long long S){
	dist[S]=0;
	cnt_path[S]=1;
	Node temp(S,0);
	q.push(S);
	long long u,v,w;
	while(!q.empty()){
		temp=q.top();
		q.pop();
		u=temp.u;
		if(visited[u])continue;
		visited[u]=true;
		for(long long i=head[u];i;i=edges[i].next){
			v=edges[i].v;
			if(dist[v]>dist[u]+edges[i].w){
				dist[v]=dist[u]+edges[i].w;
				q.push(Node(v,dist[v]));
				cnt_path[v]=cnt_path[u]%mod;
			}
			else if(dist[v]==dist[u]+edges[i].w){
				cnt_path[v]=(cnt_path[v]+cnt_path[u])%mod;
			}
		}
	} 
	
	
}
long long u,v;
int main(){
	cin>>N>>M;
	init();
	for(long long i=1;i<=M;i++){
		cin>>u>>v;
		if(u==v)continue;//自环直接去掉
		add(u,v,1);
		add(v,u,1);
	}
	Dijkstra(1);
	for(long long i=1;i<=N;i++){
		if(dist[i]!=INF)
		cout<<cnt_path[i]<<endl;
		else cout<<0<<endl;
	}
	return 0;
}

提交记录:

在这里插入图片描述

Copyright © 2002-2019 某某自媒体运营 版权所有