图论——最短路算法

这篇具有很好参考价值的文章主要介绍了图论——最短路算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

图论——最短路算法,图论,算法,图论

 引入:

如上图,已知图G。

问节点1到节点3的最短距离。

可心算而出为d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。

求最短路径算法:

1.Floyd(弗洛伊德)

是一种基于三角形不等式的多源最短路径算法。边权可以为负数

表现为a[i,j]+a[j,k]<a[i,k]。

算法思想:

枚举“中转站”(k),“起点”(i),“终点”(j)

设d[i,j]为由i点到j点的最短路径

则 图论——最短路算法,图论,算法,图论

初始化d[i,j]为无穷大 ()

算法模板如下:
 

inline int Floyd(int n,int st,int ed)// n个点,起点st,终点ed,返回st到ed的最短距离
{
    int d[n][n];
    memset(d,0x3f,sizeof(d));
    for(int i=1;i<=n;i++) d[i][i]=0;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    return d[st][ed];
}

 补充:Floyd输出最短路径。

题目:有向图中任意两点最短路径(floyd)
题目描述

  一个含n个结点的有向图(注意:是有向图!!),以矩阵存储方式给出,请求出指定的多组两个点之间的最短距离及其最短路径。

输入输出格式
输入格式:

  第1行,一个整数n(0 < n < 300 ),表示有向图中结点的个数。
  第2行到第(n+1)行,是一个n*n的矩阵,表示无向图中各结点之间的联结情况,矩阵中的数据为小于1000的正整数,其中 -1 表示无穷大!!
  第(n+2)行,一个整数m,表示接下来有m组顶点 < i , j >对 ,其中,i是起点,j是终点,且i不等于j。
  接下来有m行,每行两个整数,中间一个空格间隔,分别表示i和j,表示求解i点到j点的最短距离及最短路径。

  注:输入数据已经确保答案每一组顶点间的最短路径是唯一的,无多解数据存在,顶点编号用数字表示,从1开始编号,至n结束!

输出格式:

  共 2m 行。
  第(m-1)*2+1行,一个整数,表示第m组顶点的最短距离,若两点间距离为无穷大,则输出 -1。
  第(m-1)*2+2行,用顶点编号表示的路径序列,各顶点编号间用一个空格间隔,表示第m组顶点的最短路径,若两点间距离为无穷大,则输出的路径序列为 -1。

输入输出样例
输入样例#1:

3
0 4 11
6 0 2
3 -1 0
2
2 1
3 2 

输出样例#1:

5
2 3 1
7
3 1 2

代码如下:
 

#include<bits/stdc++.h>
using namespace std;
int n,q;
int d[10001][10001],pre[10001][10001];
void dg(int i,int j)
{
	if(i==j||pre[i][j]==0) return;
	int k=pre[i][j];
	dg(i,k);
	dg(k,j);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>d[i][j];
			if(d[i][j]==-1)
			{
				d[i][j]=0x7fffff;
			}
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(d[i][k]+d[k][j]<d[i][j])
				{
					d[i][j]=d[i][k]+d[k][j];
					pre[i][j]=k;
				}
			}
		}
	}
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		cout<<d[x][y]<<endl;
		cout<<x<<" ";
		dg(x,y);
		cout<<y;
		cout<<endl;
	}
	return 0;
}

传递闭包(连通性)


d[i,j]表示i与j是否连通。

题目:刻录光盘

题目描述

  在FJOI2010夏令营快要结束的时候,很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家,以便大家回去后继续学习。组委会觉得这个主意不错!可是组委会一时没有足够的空光盘,没法保证每个人都能拿到刻录上资料的光盘,怎么办呢?!

  DYJ分析了一下所有营员的地域关系,发现有些营员是一个城市的,其实他们只需要一张就可以了,因为一个人拿到光盘后,其他人可以带着U盘之类的东西去拷贝啊!

  他们愿意某一些人到他那儿拷贝资料,当然也可能不愿意让另外一些人到他那儿拷贝资料,这与我们FJOI宣扬的团队合作精神格格不入!!!

  现在假设总共有N个营员(2<=N<=200),每个营员的编号为1~N。DYJ给每个人发了一张调查表,让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然,如果A愿意把资料拷贝给B,而B又愿意把资料拷贝给C,则一旦A获得了资料,则B,C都会获得资料。

  现在,请你编写一个程序,根据回收上来的调查表,帮助DYJ计算出组委会至少要刻录多少张光盘,才能保证所有营员回去后都能得到夏令营资料?

输入输出格式
输入格式:

先是一个数N,接下来的N行,分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号,以一个0结束。如果一个营员不愿意拷贝资料给任何人,则相应的行只有1个0,一行中的若干数之间用一个空格隔开。

输出格式:

一个正整数,表示最少要刻录的光盘数。

输入输出样例
输入样例#1:

5
2 4 3 0
4 5 0
0
0
1 0

输出样例#1:

1

代码:
#include<bits/stdc++.h>
using namespace std;
int f[100001],d[300][300],g[100001],ans;
int main()
{
	int n;
	cin>>n;
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		while(1)
		{
			cin>>x;
			if(x==0) break;
			d[i][x]=1;
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=j&&j!=k&&k!=i)
				{
					if(d[i][k]==1&&d[k][j]==1)
					{
						d[i][j]=1;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(d[i][j]==1)
			{
				f[j]=f[i];
			}
		}
	}
	for(int i=1;i<=n;i++) 
	{
		if(f[i]==i) 
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
} 

2.dijkstra(狄克斯特拉,迪杰斯特拉)

基于贪心的单源最短路径算法。边权必须为正数

基本思想:

设d[i]为起点s到终点i的最短路径,a[i,j]为点i到点j边权。

1.找  ,并将其用k记录

2.

3.图论——最短路算法,图论,算法,图论 松弛操作,用k来更新图中所有点。

int dijkstra(int n,int st,int ed)
{
    int dis[n+1],vis[n+1];
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[st]=0;
    for(int i=1;i<=n;i++)
    {
        int k,minn=0x7fffff;
        for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<minn) minn=dis[j],k=j;
        vis[k]=true;
        for(int j=1;j<=n;j++) d[j]=min(d[j],d[k]+a[k][j]);
    }
    return d[ed];
}

堆优化dijkstra:
 

typedef pair<int,int> P;
struct node{
	int to;
	int next;
	int w;
}edge[10000010];
int head[10000010],d[10000010];
int cnt;
int n,m,x,y,z,s;
void add_edge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void dijkstra(int s)
{
	priority_queue< P,vector<P>,greater<P> >q;
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	q.push(P(0,s));
	while(!q.empty())
	{
		P p=q.top();
		q.pop();
		int u=p.second;
		if(d[u]<p.first) continue;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(d[v]>d[u]+edge[i].w)
			{
				d[v]=d[u]+edge[i].w;
				q.push(P(d[v],v));
			}
		}
	}
}

3.Bellman-Ford

O(n*m) 但有更优的,由其转换而来的Spfa算法,不再赘述。边权可以为负数

4.Spfa

基于bellman-Ford,用队列优化的单源最短路径算法,边权可以为负数,可用于判断负环。

代码如下:文章来源地址https://www.toymoban.com/news/detail-645224.html

    int head=0,tail=1;
	team[1]=s,vis[s]=1,dis[s]=0;
	while(head<tail)
	{
		head=(head+1)%10000;
		int u=team[head];
		vis[u]=0;
		for(int i=1;i<=len[u];i++)
		{
			int v=le[u][i];
			if(dis[v]>dis[u]+a[u][v])
			{
				dis[v]=dis[u]+a[u][v];
				if(vis[v]==0)
				{
					tail=(tail+1)%10000;
					team[tail]=v;
					vis[v]=1;
				}
			}
		}
	}

到了这里,关于图论——最短路算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法——图论——最短路径——Floyd / 传递闭包

    目录  Floyd-Warshall(弗洛伊德)算法 传递闭包 一、试题 算法训练 盾神与离散老师2    求所有顶点到所有顶点的最短路径问题 弗洛伊德算法(Floyd-Warshall algorithm)是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。 该算法可以处理带有负权边但不含负权环的加权

    2024年02月20日
    浏览(39)
  • 算法提高-图论-单源最短路的综合应用

    多次dijkstra求每个点到其它点的最短距离, 此时相当于建好了一张图,每个点之间的最短距离都知道了,接下来dfs搜一下怎么走最短即可 一篇博客解释了为什么一个正向建图求最小值,反向建图求最大值 根本思想是保证1到n的买卖是连通的

    2024年02月11日
    浏览(60)
  • 算法提高-图论-单源最短路的扩展应用

    多源点单终点最短路建图: 创建虚拟源点(创建虚拟源点的时候以是spfa为例 可以在建图的时候建出来,也可以在spfa这直接入队,也是虚拟源点的意思) 反向建图变成单源点多终点,然后遍历终点的dist即可找出最短路 这题挺简单的就不详细说了,主要是第一次遇到计数问题

    2024年02月16日
    浏览(47)
  • 图论算法基础:单源最短路径Dijkstra算法分析

    在 有向带权图 中给定一个起始顶点(源点),Dijkstra算法可以求出 所有其他顶点 到源点的最短路径,Dijkstra算法 不能用于同时含有正负权值的边的图 Source 顶点集合:已经确定 到源点的最短路径 的顶点就会加入 Source 集合中, Source 集合初始时只有源点 dist 数组:用于记录每个顶点到

    2024年02月11日
    浏览(42)
  • 图论与算法(遍历、最小生成树、最短路径)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫做边的集合。(x, y)表示x到y的一条双向通路,即(x, y)是无方向的;Path

    2024年04月14日
    浏览(44)
  • 图论:最短路(dijkstra算法、bellman算法、spfa算法、floyd算法)详细版

    终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。 话不多说下面看看最短路问题吧。 最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。 下面分为几类题目: 单源汇最短路--一个起

    2024年01月21日
    浏览(42)
  • 算法提高-图论-单源最短路的建图方式

    建图 找出一个牧场,它到其他牧场的距离之和最小 我是这么理解的,djsktra是一个贪心的思想,加法里面不能加负数我就不说了 求乘法最大值的时候为什么边权必须0-1,因为在乘法最大值里面有一个边权大于1的话那不就等价于求加法最小值的时候有一个边权为负数的么,d

    2024年02月08日
    浏览(44)
  • 图论14-最短路径-Dijkstra算法+Bellman-Ford算法+Floyed算法

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapter11_Min_Path 2.4.1 判断某个顶点的连通性 2.4.2 求源点s到某个顶点的最短路径 存放节点编号和距离 这里的缺点就是,更新node时候,会重复添加节点相同的node,但是路径值不一样。不影响最后结果。 更新pre数组 输出路径 初始化两

    2024年02月04日
    浏览(33)
  • 【算法每日一练]-图论(保姆级教程 篇4(最短路,分层图) #最短路计数 #社交网络 #公园 #飞行路线 # 第二短路

    目录 今天知识点   di和sp求到每个点的最短路数  floyd求到点的最短路数和经过点的最短路数 求三点最短距离 每个点有多个状态,建立分层图 求第二短路 题目:最短路计数 思路: 题目:社交网络 思路: 题目:公园 思路: 题目:飞行路线  思路: 题目:第二短路 思路:

    2024年02月04日
    浏览(41)
  • 【图论C++】Floyd算法(多源最短路径长 及 完整路径)

    UpData Log👆 2023.9.29 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述可能不够标准,但能达其意 常见的有: DJ算法 、 Floyd算法 、 A*算法 、 Bellman-Ford 算法 、 SPFA算法 其中 A*算法 是 DJ算法 的plus版, SPFA算法 是 Bellman-Ford 算法 的plus版 算法名称 DJ算法 Floyd算法 SPFA算法

    2024年02月19日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包