首页 > 其他分享 >图的最短路-Dijkstra 详解

图的最短路-Dijkstra 详解

时间：2024-01-24 18:01:03浏览次数：20  
标签：输出 int 短路 memset vis Dijkstra 详解 sizeof dis

Dijkstra

 

 

概念

注意一下，Dijkstra不适用于有负边权的图

 

 

 

就是刚开始一些点（集合B），把排序的结果放入集合A，先确定起点0，然后找集合B里面的最小值，这样才可以确定你修改的这个点的最短路在目前是最优解（后期可能改动），因为集合A的都是确定好了的最短路，所以集合A的数不做修改

松弛

很重要的一个代码

 我们假设v（终点）是3，u（起点）是1

先是1->3  最短路 dis[3](v) = 9

再进来一个中转点2，发现dis[2]+w(5) = 8    <9

于是我们dis[3]更改为8

 

朴素版-代码

#include <bits/stdc++.h>
using namespace std;

const int N=505;
struct node //存点的信息
{
	int v, w;
    //v:下一个点，w:边权
};
int n, m, u1, v1, w1, dis[N], vis[N]; 
vector<node> a[N]; //存图
void dij(int s) //dijkstra算法-用于图的最短路算法
{
	memset(dis, 63, sizeof dis); //先假设每个点的最短路径无穷大，后期才可以更新
//dis:存储最短路，源点到汇点的最短路径
	memset(vis, 0, sizeof vis); 
//vis:标记数组，用于查看点是否使用过，是否被标记
	dis[s]=0; //起点最短路径为0
	

	for (int i=1; i<=n; i++) //确定N个点的最短路径，所以n次循环
	{
		int k=0; //k:找集合B中的最小值
		for (int j=1; j<=n; j++)
			if (!vis[j] && dis[j]<=dis[k]) k=j;
		vis[k]=1; //标记，使用
		
		for (int j=0; j<a[k].size(); j++) //更改跟k相连的点的最短路
		{
			int v=a[k][j].v, w=a[k][j].w;
			if (!vis[v] && dis[v]>dis[k]+w) dis[v]=dis[k]+w; //松弛
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1}); //存图，这里是有向图
	} 
	dij(1);
	if (dis[n]==dis[0]) printf("-1");  // 不联通/无法到达
	else printf("%d", dis[n]); 
	return 0;
}

　　

练习1

第1题     最短路径 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。1≤n≤500 ,1≤m≤100000,图中涉及边长均不超过10000。

输入格式

 

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

 

输出格式

 

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

 

输入/输出例子1

输入：

3 3

1 2 2

2 3 1

1 3 4

 

输出：

3

 

样例解释

无

板子，不贴代码了，上面有

 

 

例题2

第2题     租用游艇 查看测评数据信息

长江游艇俱乐部在长江上设置了 n个游艇出租站 1,2,...,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。n≤200，保证计算过程中任何时刻数值都不超过1000000

输入格式

 

第一行中有一个正整数 n，表示有 n个游艇出租站。接下来的 n-1行是一个半矩阵r(i,j)（1≤i<j≤n）。

 

输出格式

 

输出计算出的从游艇出租站 1到游艇出租站 n所需的最少租金。

 

输入/输出例子1

输入：

3

5 15

7

 

 

输出：

12

 

样例解释

无

#include <bits/stdc++.h>
using namespace std;

const int N=505;
struct node
{
	int v, w;
};
int n, u1, v1, w1, dis[N], vis[N]; 
vector<node> a[N];
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	
	for (int i=1; i<=n; i++)
	{
		int k=0;
		for (int j=1; j<=n; j++)
			if (!vis[j] && dis[j]<dis[k]) k=j;
		vis[k]=1;
		
		for (int j=0; j<a[k].size(); j++)
		{
			int v=a[k][j].v, w=a[k][j].w;
			if (!vis[v] && dis[v]>dis[k]+w) dis[v]=dis[k]+w;
		}
	}
}
int main()
{
	scanf("%d", &n);
	for (int i=1; i<n; i++)
	{
		for (int j=i+1; j<=n; j++)
		{
			u1=i, v1=j;
			scanf("%d", &w1);
			a[u1].push_back({v1, w1});
		}
	}
	
	dij(1);
	if (dis[n]==dis[0]) printf("-1"); 
	else printf("%d", dis[n]);
	return 0;
}

　　输入方式改一改即可

 

堆优化版

 利用优先队列来找B集合内的最小值

#include <bits/stdc++.h>
using namespace std;

const int N=150005;
struct node
{
	int v, w;
	bool operator <(const node &A) const //重载运算符'<'
	{
		return w>A.w; //改成'>' 确保堆顶元素最大
	}; 
};
int n, m, u1, v1, w1, dis[N], vis[N]; 
vector<node> a[N];
priority_queue<node> q; //优先队列
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	q.push({s, 0}); //改用队列，起点的最短路仍然是0
	
	for (int i=1; i<=n; i++)
	{
		int k=q.top().v;
		q.pop(); //记得出队
		
		if (vis[k]) continue; //更新过就不用再更新了
		vis[k]=1;
		
		for (int j=0; j<a[k].size(); j++)

		{
			int v=a[k][j].v, w=a[k][j].w;
			if (!vis[v] && dis[v]>dis[k]+w) //松弛
			{
				dis[v]=dis[k]+w;
				q.push({v, dis[v]}); //！！！！记得把改过的点入队，记得入队的是"dis[v]"！！！并不是u，因为这里表示最短距离，并不是其中一个边权！！！！！
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1}); //有向
	}
	
	dij(1);
	if (dis[n]==dis[0]) printf("-1");  //到不了/不联通
	else printf("%d", dis[n]);
	return 0;
}

　　例题

第1题     最短路径（数据加强） 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。1≤n,m≤1.5×100000,图中涉及边长均不小于 0，且不超过 10000。数据保证：如果最短路存在，则最短路的长度不超过 1000000000。

输入格式

 

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

 

输出格式

 

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

 

输入/输出例子1

输入：

3 3

1 2 2

2 3 1

1 3 4

 

输出：

3

 

样例解释

无

板子，不贴代码了，上面有

 

第2题     盗谷者 查看测评数据信息

谷仓里发现谷物被盗！FJ 正试图从 C只奶牛里找出那个偷谷物的罪犯。幸运的是，一个恰好路过的卫星拍下谷物被盗前 M秒的农场的图片。这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物。约翰农场有 F草地，标号 1 到 F，还有 P条双向路连接着它们。通过这些路需要的时间在 1 到 700秒的范围内。田地 1 上建有那个被盗的谷仓。给出农场地图，以及卫星照片里每只牛所在的位置．请判断哪些牛有可能犯罪。1≤M≤700，1≤C≤100，1≤P≤100000，1≤F≤10000。

输入格式

 

第 1行：四个以空格分隔的整数：F,P,C和 M。

第 2行至 P+1行：三个空间分隔的整数，描述一个路径。连接 F1 和 F2的路径需要 T秒。

第 P+2行至 P+C+1行：每行一个整数，是一头牛的位置。

 

输出格式

 

第 1行输出嫌疑犯的数目，接下来每一行输出一只嫌疑犯的编号。

 

输入/输出例子1

输入：

7 6 5 8

1 4 2

1 2 1

2 3 6

3 5 5

5 4 6

1 7 9

1

4

5

3

7

 

输出：

4

1

2

3

4

 

样例解释

无

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
struct edge
{
	int v, w;
	bool operator <(const edge &A) const
	{
		return w>A.w;
	};
};
int f, p, c, m, u1, v1, w1, cow[N];
int dis[N], vis[N], cnt=0, ans[N];
vector<edge> a[N];
priority_queue<edge> q;
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	q.push({s, 0});
	
	while (!q.empty())
	{
		int k=q.top().v;
		q.pop();
		
		if (vis[k]) continue;
		vis[k]=1;
		
		for (int i=0; i<a[k].size(); i++)
		{
			int v=a[k][i].v, w=a[k][i].w;
			if (!vis[v] && dis[v]>dis[k]+w)
			{
				dis[v]=dis[k]+w;
				q.push({v, dis[v]});
			}
		} 
	}
}
int main()
{
	memset(cow, 0, sizeof cow);
	memset(ans, 0, sizeof ans);
	
	scanf("%d%d%d%d", &f, &p, &c, &m);
	for (int i=1; i<=p; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
		a[v1].push_back({u1, w1});
	}
	for (int i=1; i<=c; i++) scanf("%d", &cow[i]);
	dij(1);
	
	for (int i=1; i<=c; i++)
		if (dis[cow[i]]<=m) ans[++cnt]=i;
	
	printf("%d\n", cnt);
	
	sort(ans+1, ans+1+cnt);
	for (int i=1; i<=cnt; i++) printf("%d\n", ans[i]);
	return 0;
}

　　看上去是2~n的点到1，不过转化一下即可，就是把2->1, 3->1 转换成1->2，1->3即可，1到2~n，但是这题有点绕，其实就是最短路<=m即可

 

第3题     商店 查看测评数据信息

中山路上有n（n<=100）家店，每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在请帮助小明找出从一家店到另一家店之间的最短距离。n<=100，m<=1000

输入格式

 

共n+m+3行：

第1行：整数n

第2行~第n+1行：每行两个整数x和y，描述了一家店的坐标

第n+2行：整数m

第n+3行~第n+m+2行：每行描述一条通路，由两个整数i和j组成，表示第i家店和第j家店之间有通路。

第n+m+3行：两个整数s和t，分别表示原点和目标店

 

输出格式

 

仅一行：一个实数（保留两位小数），表示从s到t的最短路径长度。

 

输入/输出例子1

输入：

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

 

输出：

3.41

 

样例解释

无

#include <bits/stdc++.h>
using namespace std;

const int N=10005, oo=100005;
struct edge
{
	int v;
	double w;
	bool operator <(const edge &A) const
	{
		return w>A.w;
	};
};
struct point
{
	int x, y;
}p[N];
int n, m, x, y, u1, v1, vis[N], s, t;
double w1, dis[N];
vector<edge> a[N];
priority_queue<edge> q;
void dij(int s)
{
	for (int i=1; i<=n; i++) dis[i]=oo;
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	q.push({s, 0});
	
	while (!q.empty())
	{
		int k=q.top().v;
		q.pop();
		
		if (vis[k]) continue;
		vis[k]=1;
		
		for (int i=0; i<a[k].size(); i++)
		{
			int v=a[k][i].v;
			double w=a[k][i].w;
			if (!vis[v] && dis[v]>dis[k]+w)
			{
				dis[v]=dis[k]+w;
				q.push({v, dis[v]});
			}
		} 
	}
}
int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
	{
		scanf("%d%d", &x, &y);
		p[i]={x, y};
	}
	scanf("%d", &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d", &u1, &v1);
		int t=abs(p[u1].x-p[v1].x), t1=abs(p[u1].y-p[v1].y);
		w1=sqrt(t*t*1.0+t1*t1*1.0)*1.0;
		//cout<<w1<<endl;
		a[u1].push_back({v1, w1});
		a[v1].push_back({u1, w1});
	}
	scanf("%d%d", &s, &t);
	dij(s);
	
	printf("%.2f", dis[t]);
	return 0;
}

　　题目没有给出w，所以我们利用勾股定理求出w即可，注意输出的小数，输出的用法是 printf("%.2f" , xxxxx)

 

第4题     送件 查看测评数据信息

有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1样东西，其目的地分别是节点 2到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1样东西并且最终回到邮局最少需要的时间。1≤n≤1000，1≤m≤100000

输入格式

 

第一行包括两个整数，n和 m，表示城市的节点数量和道路数量。

第二行到第 (m+1)行，每行三个整数，u,v,w，表示从 u到 v有一条通过时间为 w的道路。

 

输出格式

 

输出仅一行，包含一个整数，为最少需要的时间。

 

输入/输出例子1

输入：

5 10

2 3 5

1 5 5

3 5 6

1 2 8

1 3 8

5 3 4

4 1 8

4 5 3

3 5 6

5 4 2

 

输出：

83

 

样例解释

无

 

#include <bits/stdc++.h>
using namespace std;

const int N=10005, oo=100005;
struct edge
{
	int v, w;
	bool operator <(const edge &A) const
	{
		return w>A.w;
	};
};
int n, m, u1, v1, w1;
int vis[N], dis[N], vis2[N], dis2[N], ans=0;
vector<edge> a[N], a2[N];
priority_queue<edge> q;
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	q.push({s, 0});
	
	while (!q.empty())
	{
		int k=q.top().v;
		q.pop();
		
		if (vis[k]) continue;
		vis[k]=1;
		
		for (int i=0; i<a[k].size(); i++)
		{
			int v=a[k][i].v, w=a[k][i].w;
			if (!vis[v] && dis[v]>dis[k]+w)
			{
				dis[v]=dis[k]+w;
				q.push({v, dis[v]});
			}
		} 
	}
}
void dij2(int s)
{
	memset(dis2, 63, sizeof dis2);
	memset(vis2, 0, sizeof vis2);
	dis2[s]=0;
	q.push({s, 0});
	
	while (!q.empty())
	{
		int k=q.top().v;
		q.pop();
		
		if (vis2[k]) continue;
		vis2[k]=1;
		
		for (int i=0; i<a2[k].size(); i++)
		{
			int v=a2[k][i].v, w=a2[k][i].w;
			if (!vis2[v] && dis2[v]>dis2[k]+w)
			{
				dis2[v]=dis2[k]+w;
				q.push({v, dis2[v]});
			}
		} 
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
		a2[v1].push_back({u1, w1});
	}
	dij(1);
	dij2(1);
	for (int i=1; i<=n; i++) ans+=dis[i]+dis2[i];
	printf("%d", ans);
	return 0;
}

　　因为要返回邮局，所以正反向各找一次即可

标签：输出,int,短路,memset,vis,Dijkstra,详解,sizeof,dis
From： https://www.cnblogs.com/didiao233/p/17985412

相关文章

  • 指标平台详解（上）：为什么有了 BI ，还需要指标平台？
    随着商业智能（BI）的快速普及与深度使用，企业在数据分析“深水区”普遍面临着指标分散定义导致口径不统一、重度依赖 ETL 作业开发报表、问题排查耗时耗力、复用率低等问题。如何兼顾敏捷与统一，实现指标的高效开发和有效管理？我们特策划了本期《指标平台详解》话题，通过两篇文章介绍指......
  • Unity3D Rts游戏里的群体移动算法是如何实现的详解
    前言实时战略（RTS）游戏是一种以管理和控制虚拟军队为主题的游戏类型。在这类游戏中，玩家需要控制大量的单位进行战斗、资源采集和建设等操作。其中，群体移动算法是实现这些操作的关键之一。本文将详细介绍Unity3DRTS游戏中群体移动算法的实现原理和代码实现。对惹，这里有一个游戏开......
  • 2024最新iOS17.3微信分身详解分享
    微信是目前最流行的社交软件之一，拥有庞大的用户群体。然而，对于一些需要同时使用多个微信账号的用户来说，使用官方版微信就显得有些不方便。iOS分身微信软件可以解决这个问题，它可以让用户在同一台设备上同时登录多个微信账号，从而实现工作生活两不误。iOS分身微信软件的优势iOS分身微......
  • C# Switch 语句进阶：模式匹配详解与实例演示
     在C#中，switch语句的模式匹配在C#7.0及以上版本中引入。以下是switch语句中常见的模式及其使用方法的示例：1.类型模式：优点： 用于检查对象的运行时类型，使代码更具可读性。publicstaticstringGetObjectType(objectobj){switch(obj){caseinti:......
  • 神经网络优化篇：详解调试处理（Tuning process）
    调试处理关于训练深度最难的事情之一是要处理的参数的数量，从学习速率\(a\)到Momentum（动量梯度下降法）的参数\(\beta\)。如果使用Momentum或Adam优化算法的参数，\(\beta_{1}\)，\({\beta}_{2}\)和\(\varepsilon\)，也许还得选择层数，也许还得选择不同层中隐藏单元的数量，也许还想使用学习......
  • SQL注入详解
    一、SQL注入注入攻击的本质，是把用户输入的数据当做代码执行。这里有两个关键条件，第一个是用户能够控制输入；第二个是原本程序要执行的代码，拼接了用户输入的数据。varsql="select*fromtableNamewherename='"+"test"+"'";这个“拼接”的过程很重要，正是这个拼......
  • Unity3D 游戏转场时如何保留节点信息详解
    Unity3D是一款非常强大的游戏开发引擎，它提供了丰富的功能和工具，使开发者能够轻松创建各种类型的游戏。在游戏开发过程中，转场是一个非常常见的需求，它可以使游戏过程更加流畅和连贯。然而，在转场过程中，如何保留节点信息是一个需要解决的问题。本文将详细介绍Unity3D游戏转场时如何保......
  • Unity3D 协程的优缺点详解
    Unity3D是一款强大的游戏开发引擎，它提供了许多功能和工具，以帮助开发者创建高质量的游戏。其中一个非常重要的功能就是协程（Coroutine）。协程是一种特殊的函数，它可以在执行过程中暂停并在稍后的时间点继续执行。在本文中，我们将详细探讨Unity3D协程的优缺点，并提供一些技术详解和代码实......
  • C# Break 和 Continue 语句以及数组详解
    C#Break它被用于“跳出”switch语句。break语句也可用于跳出循环。以下示例在i等于4时跳出循环：示例：for(inti=0;i<10;i++){if(i==4){break;}Console.WriteLine(i);}C#Continuecontinue语句在循环中发生特定条件时中断一次迭代，并......
  • C# Break 和 Continue 语句以及数组详解
    C#Break它被用于“跳出”switch语句。break语句也可用于跳出循环。以下示例在i等于4时跳出循环：示例：for(inti=0;i<10;i++){if(i==4){break;}Console.WriteLine(i);}C#Continuecontinue语句在循环中发生特定条件时中断一次迭代，并......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99