首页 > 其他分享 >SPFA && dijkstra 模版

SPFA && dijkstra 模版

时间:2024-08-24 18:49:43浏览次数:12  
标签:cnt int dijkstra vis SPFA && push dis


bool SPFA(int s)
{
	int cnt=0;
	memset(dis,0x3f,sizeof(dis));
	queue<int> q;
	q.push(s);
	vis[s]=1;dis[v]=0;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].v,w=g[u][i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return true;//有负环 
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return false; 
}





void dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push({0,s});
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue ;
		vis[u]=1;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].v,w=g[u][i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	
}

标签:cnt,int,dijkstra,vis,SPFA,&&,push,dis
From: https://www.cnblogs.com/After17/p/18378077

相关文章

  • SPFA算法
    1.spfa求最短路给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数n和m。接下来m行每行包含三个整数x,y,z,表......
  • C++ SPFA算法解析
    前言将了解C++求最短路中SPFA的算法SPFASPFA的一些说明SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(VE).!引例:输入格式给出一个有向图,请输出从......
  • Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
    说明Dijkstra:适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV)BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE)SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处......
  • 最短路 - Dijkstra 算法
    Dijkstra(迪杰斯特拉)算法是基于贪心思想的单源最短路算法暴力Dijkstra具体如下:structnode{ intv,w;};vector<node>e[N];intdist[N],vis[N];e[u]存的是节点u的所有出边的终点和边权,dist[u]存u到原点s的最小距离,vis[u]标记是否走过voiddijkstra(int......
  • 《数据结构》最短路径Dijkstra算法
                                    最短路径Dijkstra算法分析生长点ABCDEFP(A)=FAD(A)=130P(B)=FBD(B)=24P(C)=FCD(C)=10P(D)=——D(D)=无穷P(E)=——D(E)=无穷CP(A)=FAD(A......
  • 迪杰斯特拉(Dijkstra)算法(C/C++)
    迪杰斯特拉(Dijkstra)算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻(EdsgerDijkstra)在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法,每次遍历到始......
  • 以node / link文件表征的道路网络-----dijkstra算法yyds-----基于南京公路公开数据做
    前文已经基于公开数据,获得了南京的全域高速公路的路网数据,这些以node/link文件表征的道路网络不仅延续了osm地图中所包含的经纬度、名称、容量等信息,还包含了一个重要的道路等级字段“link_type_name”。交通部门一般以高速公路、国省干道、城市道路、乡道农路作为区分......
  • 最短路(DJsktra,spfa,flyd).md
    最短路弗洛伊德:全源最短路:\[\LargeDP方程:\\dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])\]#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#defineintlonglong#defineiosstd::ios::sync_with_stdio(false);s......
  • 基于Dijkstra、A*和动态规划的移动机器人路径规划(Matlab代码实现)
     ......
  • Dijkstra算法
    Dijkstra算法是一种用于在加权图中寻找单源最短路径的算法。它由荷兰计算机科学家EdsgerDijkstra在1956年提出。该算法基于贪心策略,通过不断选择当前最短路径上的顶点来逐步确定最短路径。它使用一个距离数组来记录起始点到每个顶点的距离,并使用一个集合来存储已经求得最短路......