精华内容
下载资源
问答
  • 求解两点最短路径的算法

    千次阅读 2020-07-19 23:42:40
    最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的...多源最短路算法:求任意两点之间的最短路径.

    最短路径算法

    • 单源最短路算法:已知起点,求到达其他点的最短路径。
              常用算法:Dijkstra算法、Bellman-Ford算法、SPFA算法。
    • 多源最短路算法:求任意两点之间的最短路径。
              常用算法:Floyd算法。

    1.Dijkstra算法

            迪杰斯特拉算法(Dijkstra)是寻找从一个顶点到其余各顶点最短路径的算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
            处理问题:单源、无负权、有向图、无向图最短路径。
            不能使用的情况:边中含有负权值(无法判断)。
            主要特点:以起始点为中心向外层层扩展,直到扩展到终点为止。
            算法过程:V为顶点集合,分为两组S和U。其中,S为已求出的顶点的集合(初始时只含有源点V0),U为尚未确定的顶点集合,源点到各个顶点最短路径的距离结果存在dist[]中。
                            1.初始化:S只包含源点,U包含除V中S以外的其他点;
                            2.选择:从U中选取一个距离源点最近的顶点u加入S;
                            3.更新:修改u的后继顶点的最短路径长度;
                            4.重复步骤2和3直到所有顶点都包含在S中。
           举例说明:图中有A、B、C、D、E五个顶点,其中A为源顶点,寻找A到其他各顶点的最短路径。
                            Step1:V包含A、B、C、D、E五个点,S只包含源点A,U包含V中除S以外的其他点,计算U中各点到源点的距离发现距源点最近的顶点是B;在这里插入图片描述                        Step2:将距源点最近的顶点B移入S中,S包含A、B,U包含C、D、E,再次计算U中各点到源点的距离发现距源点最近的顶点是C;在这里插入图片描述                        Step3:再次将距源点最近的顶点C移入S中,S包含A、B、C,U包含D、E,再次计算U中各点到源点的距离发现距源点最近的顶点是E;在这里插入图片描述                        Step4:再次将距源点最近的顶点E移入S中,S包含A、B、C、E,U包含D,再次计算U中各点到源点的距离发现距源点最近的顶点是D;在这里插入图片描述                        Step5:再次将距源点最近的顶点D移入S中,S包含A、B、C、E、D,U为空,算法结束,得到的dist[]中的结果就是A到其他各顶点的最短距离。在这里插入图片描述

    2.Bellman-Ford算法

           贝尔曼-福特算法(Bellman–Ford)是求解单源最短路径问题的一种算法,它的原理是对图进行次松弛操作,得到所有可能的最短路径。其算法可以进行若干种优化,提高了效率。
           基本思想: Bellman-Ford的思想和Dijkstra很像,其关键点都在于不断地对边进行松弛,而最大的区别就在于前者能作用于负边权的情况。其实现思路是在求出最短路径后,判断此刻是否还能对便进行松弛,如果还能进行松弛,便说明还有负边权的边。
           处理问题:单源、可有负权、有向图、无向图最短路径。
           算法过程:1.初始化:初始化所有的点,每一个点保存一个值,表示源点到这个点的距离其他点的值设为无穷大;
                            2.迭代求解:进行循环,从1到n-1,进行松弛计算;
                            3.检验负权回路:遍历所有边,如果的d[v]>d[u]+w(u,v)存在,则有从源点可达的权为负的回路。
           边的松弛操作:如下图所示,d[v]、d[u]是目前s到v、u的最短距离,关注边<u,v>能否改善d[v]的值。如果if(d[u]+w<d[v])成立,原有的d[v]路线将被s\rightarrowu\rightarrowv代替,这就是边<u,v>的松弛操作。在这里插入图片描述

    3.SPFA算法

           SPFA 算法是Bellman-Ford算法的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环,它采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。
           处理问题:单源、可有负权、有向图、无向图最短路径(自身其实无法处理负权)
           算法思想:设立一个队列用来保存待优化的点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

    4.Floyd算法

           弗洛伊德算法(Floyd)又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法,也要高于执行|V|次SPFA算法。
           处理问题:多源、可有负权、有向图、无向图最短路径。
           优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
           缺点:时间复杂度比较高,不适合计算大量数据。
           算法过程:1.从任意一条单边路径开始,所有两点之间的距离是边的权,用邻接矩阵G表示,如果两点之间没有边相连,则权为无穷大;
                            2.对于每一对顶点i和j,看看是否存在一个顶点k使得从i到k再到j比已知的路径更短。G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,定义一个矩阵D用来记录所插入点的信息,则D[i][j]=k。
                                          forkinrange(self.V):for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}k{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V):
                                                 foriinrange(self.V):for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}i{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V):
                                                        forjinrange(self.V):for{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}j{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}} in {_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}range(self.V):
                                                               ifself.G[i][k]+self.G[k][j]<self.G[i][j]:if{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.G[i][k]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}+self.G[k][j]<self.G[i][j]:
                                                                      self.G[i][j]=self.G[i][k]<self.G[k][j]self.G[i][j]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}={_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.G[i][k]<self.G[k][j]
                                                                      self.D[i][j]=self.D[i][k]self.D[i][j]{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}={_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}{_{}}self.D[i][k]
           举例说明:图中有1、2、3、4、5五个顶点,寻找任意两点间的最短路径。矩阵G为任意两点间的权值邻接矩阵,矩阵D为用来记录所插入点的标号。
                            Step1:初始化矩阵G、D,G初始化为任意两点间的距离,若两点间没有直线相连则用无穷大表示;D初始化为任意两点间的终点标号。在这里插入图片描述                        Step2:更新矩阵G、D,看有没有任意两点经过0之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第0列的元素。在这里插入图片描述                        Step3:继续更新矩阵G、D,看有没有任意两点经过1之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第1列的元素。在这里插入图片描述                        Step4:继续更新矩阵G、D,看有没有任意两点经过2之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第2列的元素。在这里插入图片描述                        Step5:继续更新矩阵G、D,看有没有任意两点经过3之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第3列的元素。在这里插入图片描述                        Step6:继续更新矩阵G、D,看有没有任意两点经过4之后比原来的路径更短,有的话G中对应的元素更新为更小的值,D中对应的元素更新为同一行第4列的元素。算法结束,得到的G4{G_{4}}为任意两点间的最短距离,D4{D_{4}}为任意两点间最短路径间的信息。在这里插入图片描述

    几种最短路径算法的对比

    Dijkstra算法、Bellman-Ford算法和SPFA算法的对比

    • Dijkstra算法无法判断含负权边的图的最短路径,Bellman-Ford算法优于Dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高。
    • SPFA算法在负边权图上可以完全取代Bellman-Ford算法,另外在稀疏图中也表现良好。但是在非负边权图中,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法,以及它的使用堆优化的版本。
    • 与Dijkstra算法与Bellman-Ford算法都不同,SPFA的算法时间效率是不稳定的,即它对于不同的图所需要的时间有很大的差别。

    Dijkstra算法和Floyd算法的对比

    • Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。
    • Floyd算法是多源最短路径算法,用于计算任意两点间的最短路径。
    • Dijkstra算法是基于贪心算法的思想,从起点出发逐步找到通向终点的最短距离;而Floyd算法是基于动态规划的思路,通过循环迭代的方法同时找出任意两个顶点间的最短距离。
    展开全文
  • 算法设计与分析、Floyd算法、最短路径问题、任意两点之间的最短距离、

    前言

    关于最短路径的问题,我在上一篇文章《算法设计与分析——Dijkstra算法》中已经提到过了。但是,本篇我们需要讲解的Floyd算法,其解决的最短路径问题与Dijkstra算法有些许不同。
    在《算法设计与分析——Dijkstra算法》中,我们就强调过,Dijkstra算法是一种单源点最短路径算法,什么是单源点最短路径算法?即在连通图中,我们从一个指定的点(这个就是源点)出发,寻找该点到连通图中其他所有点的最短路径及距离。而Floyd算法,其寻找的是连通图中任意一点到其他所有点的最短路径(我们讲解的过程中注重的是最短路径的距离,如果需要具体的路径,算法运行中做下记录即可),这是一个不同点。
    再者,就是算法的核心思想问题,Dijkstra算法采用的是贪心算法(也称贪婪算法),即满足当前最优,以此来达到我最终结果的最优。Floyd算法则是利用的动态规划思想,利用子问题最优解,而来达到最终问题的最优解。二者有相似,但又不同。
    那么,不废话了,接下来我们就来具体分析一下Floyd算法

    一、算法思想分析

    首先,我们来了解一下Floyd算法面对的问题:

    • 问题:给定一个加权连通图,要求找到从每个顶点到其他所有顶点之间的路径。

    那么,Floyd算法是如何解决这个问题的呢?
    接下来的内容可能有点绕,请大家慢慢阅读。
    我们来想象一下,连通图中存在n个顶点,我们依次以这n个顶点作为中间点,什么是中间点?例如:a→b、b→c,如果我们要达成a→c的路径,这个时候b就是中间点。
    在选好中间点后,就要开始构造最短路径了,我们的问题是什么?每个顶点到其他顶点之间的最短路径,那么我们肯定要遍历每个顶点到其他顶点吧?所以,选好中间点后,遍历每个点到其他顶点的路径(这里其实获取的是距离)。中间点这个时候的作用就体现到了,这个时候我们有一个选好的中间点,假设我们当前选到的中间点是c而我们当前遍历到的顶点路径是a→d,那么在这种情况下a→d所达成的最短路径距离就有两种构成,是之前已经记录过的a→d的最短路径(这个记录的最短路径,可能是我们利用前面的中间点获取到的zu),是a以c为中间点,然后抵达d的距离(即a→c,c→d的距离之和),这个就是当前情况下我们能够获取到的a→d的距离的两种方案,而要最短,即取二者最短存入即可。
    上面是具体分析了一下,接下来我们简单总结一下:

    • 首先遍历所有点,将其作为中间点;
    • 在获取一个中间点后,开始分析每一个点到其他点的路径的情况,取最短路径距离为之前记录过的该点到另外一个点的最短距离和该点到中间点的最短路径距离加中间点到另外一个点的距离(有点像绕口令,希望大家能明白)中最短的那个。
    • 重复第二步操作,知道所有点都已经作为中间点,这个时候我们就获取到每一个顶点到另外一个点的最短路径(距离)。

    再总结一下Floyd算法最短路径的计算公式:
    Floyd总结
    说句大白话就是,我到一个地方,我要么用以前的方法过去,要么我途径某个地方,再从这个地方到目的地。当然,这只是个比喻。
    单独文字的话肯定过于枯燥,我们来举个《算法设计与分析基础》书中的栗子分析一下:
    《算法设计与分析基础》例题分析
    上图中表示连通图的方式是邻接矩阵的方式,第一个矩阵中0表示自己到自己,肯定距离为0,∞表示暂时不可达(不能直接抵达),其他数字则表示两点间的距离(路径权值)。
    但是,我给出的C语言代码将会不一样,也就是矩阵定义的规则变了一下,其他仍然相通。

    二、算法代码

    C语言

    我前面几篇文章都是算法效率分析在前,我觉得这样的顺序似乎有些问题,在本篇文章我先贴出代码,在写出算法效率分析,其效果可能会好一点。
    对于接下来我给出的代码,我有一点有说明一下,我给出的邻接矩阵规则不一样,-1表示不可达,0表示自己到自己,其他值则表示两点间距离。但这样其实给自己的代码加了一点工作量,这并不是一个聪明的做法,大家有自己的想法可以进行适当更改的。
    注意,一开始用户输入的矩阵和最后获取到的矩阵,其意义已经改变。

    /*
    动态规划算法-加权连通图中任意两点间的最近距离-Floyd算法
    输入:连通图的带权邻接矩阵 其中-1表示 不可达
    输出:计算后的任意两点间的最短距离的邻接矩阵(类似于传递闭包的邻接矩阵 但是值表示的是距离 -1表示不可达)
    例如:
    输入:
    0 -1 3 -1
    2 0 -1 -1
    -1 7 0 1
    6 -1 -1 0
    输出:
    0 10 3 4
    2 0  5 6
    7 7  0 1
    6 16 9 0
    */
    #include<stdio.h>
    #define MAXN 1000
    int input[MAXN][MAXN];
    int min( int a, int b ) {
    	return a < b ? a : b;
    }
    void Floyd(int n) {
    	for(int k=1; k<=n; k++) {
    		for(int i=1; i<=n; i++) {
    			if(i==k) continue; // 节省计算量
    			for(int j=1; j<=n; j++) {
    				if(j==k) continue; // 同样 节省计算量 
    				int sum;
    				// 这里有一个问题 我们给出的公式其实蛮简单 为什么我们这里写的这么复杂呢?
    				// 因为。。。我定的是-1为不可达 所以必须做一些特殊处理 这里的话我属于取巧的 
    				// 大家可以自行更改这个部分, 不可达的定义也可以自己更改 
    				if(input[i][k]==-1||input[k][j]==-1) sum=-1; // 对于求和的 如果一旦其中一个不可达 结果就是不可达 
    				else sum=input[i][k]+input[k][j];
    				if(input[i][j]==-1&&sum==-1) input[i][j]=-1; // 这里就是 如果两个都不可达 则最终结果就不可达 
    				else if(input[i][j]!=-1&&sum==-1) input[i][j]=input[i][j]; //  
    				else if(input[i][j]==-1&&sum!=-1) input[i][j]=sum;  // 其中一个可达 就取可达的距离 
    				else  input[i][j]=min(input[i][j],sum); // 两个都可达 则取最短的距离 
    			}
    		}
    	}
    }
    int main() {
    	printf("输入有向图的顶点数n:");
    	int n;
    	scanf("%d",&n);
    	printf("输入有向图的带权邻接矩阵(-1表示不可达):\n");
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			scanf("%d",&input[i][j]);
    		}
    	}
    	Floyd(n);
    	printf("任意两点最短路径的邻接矩阵:\n");
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			printf("%d ",input[i][j]);
    		}
    		printf("\n");
    	}
    }
    

    代码如上,如果大家对代码有任何建议,欢迎提出,也欢迎大家贴出自己更高效的代码在留言区,谢谢。
    这次的JavaScript代码又鸽了,我以后有时间一定补上!

    三、算法效率分析

    其实从代码中我们就可以看出,有三层嵌套循环,那么算法效率肯定是n的立方级别。
    那么对于Floyd算法,算法复杂度其实同样介于O(n²)~O(n³),这是估计来说,但是如果严格来说的话,Floyd算法的算法复杂度还是应该是O(n³)

    后记

    对于后面这几篇文章分析的算法,其算法效率可能并没有前面的算法来的高,但是,还是那句话,一个算法是解决问题的,那么在解决这个问题的所有算法中进行比较,那才有意义。这些算法,我觉得更重要的是其中的思想,了解其中的一些关键处理,用解决这一个问题的算法思想,去高效的解决另一个问题,这样或许更不错,是吧?

    感谢你看到这里。

    展开全文
  • 给定M*N的矩阵,其中的每个元素都是-10到10之间的整数。你的任务是从左上角(1,1)走到右下角(M,N),每一步只能够向右或者向下,并且不能够走出矩阵的范围。你所经过的方格里的数字都必须被选取,请找出一条最...
  • 单源点最短路径

    千次阅读 2016-01-08 10:02:25
    单源点最短路径---雨竹清风单源最短路径:是从某一个源点s出发到图中的所有的顶点之间的最短路径。1.单源点最短路径的变体:1)单终点最短路径问题:找到从每一个顶点到终点的最短路径。可以将图中的边全部反向,然后...

    单源点最短路径

    ---雨竹清风

    单源最短路径:是从某一个源点s出发到图中的所有的顶点之间的最短路径。

    1.单源点最短路径的变体

    1)单终点最短路径问题:找到从每一个顶点到终点的最短路径。可以将图中的边全部反向,然后求单源点最短路径即可。

    2)单对顶点最短路径问题:对于图中的两个顶点uv,找到从uv的最短路径。

    3每对顶点间最短路径问题:找到图中的每对顶点之间的最短路径。

    知识点:

    最短路径的子结构:

    引理:最短路径的子路径是最短路径。

    这是动态规划和贪心的算法。

    负权值边:

    负权值是指边上的权值是负数,比如罚款。若图中存在负权回路,那么最短路径的定义就不对了,因为每次经过负权回路总是能够得到更小的权值。

    回路:

    最短路径会包含回路吗?最短路径是不会包含回路的,不仅不能包含负权回路,而且是不能包含正权回路。因为若路径上存在一个环,我们将环移除之后便是一条更短的路径,所以说一条最短路径上不可能存在正权环。

    零权回路:

    零权回路是指路径上存在一个环,环的权值是0,所以可以通过移除零权环路,便得到一条从源点sv的一条无环回路。

    2.最段路径的表示

    最短路径上的顶点是源点可达的顶点的集合。最短路径树上的每一条路径便是从源点到某一个顶点的最短路径。[最短路径树:从源点到源点可达的顶点之间存在一条最短路径,这些最短路径便构成了最短路径树]在最短路径树上,源点到某一个顶点之间的唯一的简单路径便是从源点到该顶点的最短路径。

    单源点最短路径 - 雨竹清风 - 雨竹清风的博客
    单源点最短路径 - 雨竹清风 - 雨竹清风的博客
    绿色的边标出的是一棵以源点v0为根的最短路径树。

     知识点:

    松弛技术:

    松弛表示紧缩上届的操作,即对于从源点到该结点的最短路径的修改。若用d.ud.v表示从源点到uv的最短路径 ,那么d.v d.u+w(u,v)这个不等式必须满足,这个不等式的约束是比较松弛的,所以称为松弛技术。若在松弛之前d.v >d.u+w(u,v),那么经过松弛之后,即条件满足修改d.v的值,令d.v = d.u+w(u,v),因此d.v的值会减少。若在松弛之前d.v d.u+w(u,v),那么d.v不会修改。

    3.Bellman-Ford算法

    解决的问题:Bellman-Ford算法能够在一般的情况(存在负权环路)下,解决单源点最短路径问题。

    Bellman-Ford算法将对每一条边进行松弛操作,共进行|v|-1次;本算法将会返回一个布尔值,布尔值的作用是判断该图中是否存在负权回路,若该布尔值为false则存在负权回路,那么问题无解,否则问题有解。

    伪代码如下:

    单源点最短路径 - 雨竹清风 - 雨竹清风的博客

    为什么循环n-1次即可?

    因为最短路径肯定是个简单路径,不可能包含回路的,如果包含回路,且回路的权值和为正的,那么去掉这个回路,可以得到更短的路径。如果回路的权值是负的,那么肯定没有解了,图有n个点,又不能有回路,所以最短路径最多n-1边。又因为每次循环,至少relax一边,所以最多n-1次就行了。

    为什么还需要进行检测是否存在负权环?

    因为对于图中的n-1次松弛操作并没有保证一定没有负权环,若有负权环,那么对于图中进行n-1次松弛操作结论依然成立。所以一定要检测是否存在负权环。

    检测负权环的思想:将图中所有的边进行一次检测,检查是否存在(u,v,w)这么一条边,使得v.d > u.d + w,若存在则说明会有负权环的存在,所以问题无解。若不存在,那么有解。

    图解bellman-ford算法:

    给定一个松弛边的顺序:

    (t,x) (t,y) (t,z) (x,t) (y,x) (y,z) (z,x) (z,s) (z,t)

    原图:

    顶点上的值代表从源结点sv的最短路径上权值的上界,初始化为无穷。

    单源点最短路径 - 雨竹清风 - 雨竹清风的博客
    单源点最短路径 - 雨竹清风 - 雨竹清风的博客

     单源点最短路径 - 雨竹清风 - 雨竹清风的博客
     

     

     


    展开全文
  • 问题描述:设计一个算法,计算出给定二叉树中任意2个结点之间的最短路径。编程任务:对于给定的二叉树,和二叉树中结点对,编程计算结点对之间的最短路径。数据输入:由文件input.txt给出输入数据。第1行有1...

    文章作者:Slyar文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

    数据结构课的实验题目,涉及到LCA问题,这次暴力解决了,以后学了NB算法回来做个对比...

    问题描述:

    设计一个算法,计算出给定二叉树中任意2个结点之间的最短路径。

    编程任务:

    对于给定的二叉树,和二叉树中结点对,编程计算结点对之间的最短路径。

    数据输入:

    由文件input.txt给出输入数据。第1行有1个正整数n,表示给定的二叉树有n个顶点,编号为1,2,…,n。接下来的n行中,每行有3个正整数a,b,c,分别表示编号为a的结点的左儿子结点编号为b,右儿子结点编号为c。各结点信息按照层序列表的顺序给出。

    文件的第n+2行是1个正整数m,表示要计算最短路径的m个结点对。接下来的m行,每行2 个正整数,是要计算最短路径的结点编号。

    结果输出:

    将编程计算出的m个结点对的最短路径长度输出到文件output.txt。每行3 个正整数,前2 个是结点对编号,第3 个是它们的最短路径长度。

    输入文件示例input.txt

    9

    1 2 3

    2 4 5

    3 0 0

    4 0 0

    5 6 7

    6 0 0

    7 8 9

    8 0 0

    9 0 0

    5

    6 9

    3 8

    4 7

    2 9

    4 6

    输出文件示例output.txt

    6 9 3

    3 8 5

    4 7 3

    2 9 3

    4 6 3

    Tips:因为题目中的2句话,使得这题变得很简单...

    1、"第1行有1个正整数n,表示给定的二叉树有n个顶点,编号为1,2,…,n"

    2、"各结点信息按照层序列表的顺序给出"

    第一句话说明如果我们用数组来存结点,并且从下标1开始,那么结点的值和结点的下标是一样的...

    第二句话说明编号小的结点一定在编号大的结点的上方...

    这样我们只需要求出2个结点到最近公共祖先结点的路径长度,然后将其相加就可以得到2个结点的最短路径了...

    不过 最近公共祖先(Least Common Ancestors) 问题貌似还是比较高级的玩意,貌似还要用并查集...反正咱现在不会,以后研究了再修改...

    /*

    求二叉树任意两节点最短路径长度

    Slyar

    http://www.slyar.com

    2009.5.22

    */

    #include

    #include

    /* 二叉树节点定义 */

    typedef struct node

    {

    int data;

    int lchild;

    int rchild;

    }bitree;

    /* 定义全局变量 */

    int n, dis, sign;

    bitree *t;

    /* 函数声明 */

    int Search(int);

    int ShortestPath(int, int);

    int GetPathLength(int, int);

    /* 主函数 */

    int main()

    {

    int i, m, a, b, c;

    int start, end;

    int length;

    /* 定义文件指针 */

    FILE *fp1, *fp2;

    /* 以只读方式打开输入文件 input.txt */

    if((fp1 = fopen("input.txt","r")) == NULL)

    {

    printf("Cannot open this file./n");

    exit(0);

    }

    fscanf(fp1, "%d", &n);

    /* 动态分配空间 */

    t = (bitree*) calloc(n + 1, sizeof(bitree));

    /* 读入二叉树 */

    for (i = 1; i <= n; i++)

    {

    fscanf(fp1, "%d%d%d", &a, &b, &c);

    t[i].data = a;

    t[i].lchild = b;

    t[i].rchild = c;

    }

    fscanf(fp1, "%d", &m);

    /* 以写入方式打开输出文件 output.txt */

    if((fp2 = fopen("output.txt","w")) == NULL)

    {

    printf("Cannot open this file./n");

    exit(0);

    }

    while (m--)

    {

    fscanf(fp1, "%d %d", &start, &end);

    /* 求解最短路径 */

    length = ShortestPath(start, end);

    fprintf(fp2, "%d %d %d/n", start, end, length);

    }

    /* 关闭输入文件 */

    fclose(fp1);

    /* 关闭输出文件 */

    fclose(fp2);

    /* 注销分配的空间 */

    free(t);

    return 0;

    }

    /* 计算最短路径,找最近的共同祖先结点 */

    int ShortestPath(int start, int end)

    {

    int i;

    int dis1, dis2;

    /* 共同祖先节点肯定在序号较小结点的上方 */

    for (i = (start < end ? start:end); i > 0; i--)

    {

    /* 求start节点的祖先结点路径长度 */

    sign = 0;

    dis = 0;

    dis1 = GetPathLength(i, start);

    /* 求end节点的祖先结点路径长度 */

    sign = 0;

    dis = 0;

    dis2 = GetPathLength(i, end);

    /* 如果有共同祖先结点则最短路径为两路径之和 */

    if (dis1 != 0 && dis2 != 0)

    {

    /* 小于0说明起始结点就是要找的,路径长度应为0 */

    if (dis1 < 0) dis1 = 0;

    if (dis2 < 0) dis2 = 0;

    return dis1 + dis2;

    }

    }

    }

    /* 求以start为根的二叉树中编号为key的结点路径长度 */

    int GetPathLength(int start, int key)

    {

    /* 遇到叶子结点停止递归 */

    if (start != 0)

    {

    /* 找到key就返回。如果起始结点就是要找的,返回-1 */

    if (t[start].data == key)

    {

    sign = 1;

    return -1;

    }

    /* 没找到则递归搜索左子树 */

    if (!sign) GetPathLength(t[start].lchild, key);

    /* 没找到则递归搜索右子树 */

    if (!sign) GetPathLength(t[start].rchild, key);

    /* 找到key后返回,每次路径长度+1 */

    if (sign) dis++;

    }

    return dis;

    }

    展开全文
  • 主要为大家详细介绍了JS实现深度优先搜索求解两点最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 主要讲述了利用粒子群算法做改进,找寻所有给定节点位置,任意节点之间的最短路径
  • %对这个变量即我们刚刚绘制的图形进行高亮处理 补充: 求出任意两点最短路径矩阵 %求出任意两点最短路径矩阵 D=distances(G); %注意:该函数matlab2015b之后才有 D(1,2)% 1 -> 2的最短路径 D(3,9)% 3 -> 9的最短...
  • 寻求从初始值(row0,col0)到末值(row,col)最短路径是多少 例: 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 在两点之间一定能到达的前提下。。。。。要不然就没意思了。。。 #include<iostream> using ...
  • 给定两个顶点,给出两个顶点的最短路径(如果没有连通,请给出)。把图进行可视化展示(一个适当大小的图),同时把计算的结果可视化展示。 环境 操作系统: Windows 10 X64 IDE: visual studio 2017 语言:C# ...
  • 单源点最短路径  单源点最短路径问题:给定图G=(V,E),每条边(i,j)上都标有非负实数C[i][j]作为它的权;在图中指定一个顶点v作为源点,求从v到其他每个顶点的最短路径长度。单源最短路问题的进一步推广是求每对...
  • Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意个顶点之间的最短路径
  • 给定一个乡镇网络图,求取个乡镇的最短路径,并输出路径,以及路径距离的大小。
  • 在非网图中,最短路径是指两点之间经历的边数最少的路径。 单源最短路径 所谓“单源最短路径问题”,是指给定一个带权有向图G和源点V0,求从V0到其他各顶点的最短路径。 Dijkstra算法是,按距离递增的顺序逐步找出V0...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,047
精华内容 10,418
关键字:

给定两点最短路径