精华内容
下载资源
问答
  • 数据结构8——最短路径

    千次阅读 2020-12-23 14:45:23
    一、最短路径最短路径:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。求最短路径的四个算法如下:二、算法概述【Dijkstra算法】单源最短路:从单个源点出发,到所有结点的最短路作用:...

    一、最短路径

    最短路径:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。

    求最短路径的四个算法如下:

    二、算法概述

    【Dijkstra算法】

    单源最短路:从单个源点出发,到所有结点的最短路

    作用:计算正权图上的单源最短路。

    图类型:有向图、无向图。

    限制:边权为正。

    【Bellman-Ford算法】

    事实1:当负权存在时,连最短路都不一定存在。

    事实2:如果最短路存在,一定存在一个不含环的最短路。

    作用:计算图上的单源最短路(前提是最短路存在)。

    图类型:有向图、无向图。

    优势:边权可为负。

    【Floyd算法】

    作用:求出每两点之间的最短路。

    图类型:有向图、无向图。

    特点:如果要用Dijkstra或Bellman-ford求出每两点之间的最短路,那么需要调用n次Dijkstra(边权均为正)或者Bellman-ford(有负权)。

    三、负权问题

    如果一个图仅仅是存在负权,但不构成负权回路,又该如何?

    Dijkstra 算法

    观察上图,若 A 作为源点,在第一轮循环后,B 被标记数组标记,但我们发现在第二轮循环中,B 还可以通过 C 点继续进行更新。由此,可以得出结论:Dijkstra 算法不适用于负权图。

    Bellman_Ford 算法和 SPFA 算法

    我们先思考下上述 “因 B 点被标记数组标记而导致无法通过 C 点再更新” 的问题,归根结底是标记数组的锅。有人提议,不妨去掉标记数组,如果去掉,就会造成很严重的问题,首当其冲的是“无法求出dist[]的最小值”。

    反观 Bellman_Ford 算法和 SPFA 算法,它们不存在标记数组的问题,因此对于仅仅存在负权的图,它们都可以工作的很好。

    最后,读者需要注意的是,如果是无向图,只要存在一条负边,该图就存在负权回路,这不难理解,无向图的一条边相当于有向图的往返两条边。

    四、补充分析

    Dijkstra,Bellman_Ford 和 SPFA,该用哪个?

    Bellman_Ford 没什么好说的,能不用就不用。

    国际上一般不承认 SPFA 算法,因为在 SPFA 算法论文中对它的复杂度证明存在错误,其次 Bellman_Ford 的论文中已提及过这个队列优化。

    SPFA 算法有两个优化策略 SLF 和 LLL。

    SLF,Small Label First 策略,设要加入的节点是 j,队首元素为 i,若dist[j] < dist[i],则将 j 插入队首,否则插入队尾;

    LLL,Large Label Last 策略,设队首元素为 i,队列中所有 dist 值的平均值为 x,若dist[i] > x则将 i 插入到队尾,查找下一元素,直到找到某一 i 使得dist[i] <= x,则将 i 出队进行松弛操作。

    SLF 可使速度提高 15 ~ 20%,SLF + LLL 可提高约 50%。 在实际的应用中 SPFA 的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的 Dijkstra 算法。

    使用邻接表 + 二叉堆优化的 Dijkstra 算法,复杂度适宜,也稳定,就是有个缺陷,不能处理负权回路。

    最后话个唠,我发现在算法竞赛中我们大多数的选择还是 SPFA,知乎了下,邻接表 + 二叉堆优化的 Dijkstra 写起来复杂,容易错,而 SPFA 代码简单,容易写,但是会被题目卡数据。

    总结:首选 Dijkstra,其次 SPFA,最后 Bellman_Ford,具体采用哪种方法,视情况而定。

    展开全文
  • 上一篇博文我们提到了图的最短路径问题:两个顶点间的最短路径该如何寻找?其实这个问题不应该叫“最短”路径问题,而应该叫“最便宜”路径问题,因为有时候我们会为图中的边赋权(weight),也叫权重,相当于经过一条...

    上一篇博文我们提到了图的最短路径问题:两个顶点间的最短路径该如何寻找?其实这个问题不应该叫“最短”路径问题,而应该叫“最便宜”路径问题,因为有时候我们会为图中的边赋权(weight),也叫权重,相当于经过一条边的“代价”,一般为正数。比如下图(边旁的数字即该边的权重)

    如果单纯考虑一条路径上边的条数,那么从v0到v6的最短路径应该是:v0-v3-v6。但是如果考虑边的权重,从v0到v6的“最便宜”路径应该是:v0-v1-v4-v6,其总权重为3(路径中所有边的权重之和),而如果走v0-v3-v6的路径,总权重将是11。

    边有权重的图我们称之为赋权图,反之称为无权图,赋权图显然可以比无权图应用于更多场合,比如用赋权图来表示城市间公路,权重越大路况越差,或者权重越大,过路费用越高等等。

    其实不考虑权重的最短路径问题就是所有边的权重都是1的“最便宜”路径问题,比如将上图的所有边去掉权重后的无权图也可以这样表示:

    方便起见,我们就将“最便宜”路径称为最短路径。

    接下来让我们先从简单的无权情况开始,看看如何找两个顶点间的最短路径。不过到了这一步,一件有意思的事情需要说明一下,那就是:找X到Y的最短路径,比找X到所有顶点的最短路径更慢(有权无权都是如此)。

    出现这个情况的原因我们可以简单的分析一波:找X到Y的最短路径,最直接的做法就是令程序从X出发沿着可行的边不断的走,直到走到Y处为止,但是当走到Y处时,没人能保证刚刚走的那条路就是最短的,除非你走遍了整个图的顶点,换句话说,你要确定走到Y处且走的路径是最短的,你就得走遍所有顶点,而且在这个过程中你必须不断记录各个路径的长度,不然当你发现到一个顶点有多条路径时怎么比较它们呢?所以,你要找X到Y的最短路径,你就得找出X到所有顶点的最短路径。

    当然,也存在专门寻找点对点最短路径的思路,但是目前来说,单独找X到Y的最短路径不会比找X到所有顶点的最短路径更快,所以我们接下来探讨的问题其实都是:单源最短路径问题。即给定一个起点(源),求出其与所有顶点的最短路径。有了到所有顶点的最短路径,我们自然也就有了到给定顶点Y的最短路径。

    对无权图进行单源最短路径寻找的思路,就是我们上面所说的“最直接的做法”。为了更方便讲解,我们假定若存在边(A,B),则B是被A“指向”的顶点。那么对无权图进行单源最短路径寻找就是这样的:

    首先,我们将起点的路径长设为0,其他顶点路径长设为负数(也可以是其他不可能的值,图例中用?表示),下例以v1作为起点

    接着我们将起点所指向的顶点的路径长设为1,可以肯定的是,只有被路径长为0的起点所指向的顶点的路径长为1,本例中即v3和v4:

    接下来,我们将路径长为1的顶点(v3和v4)所指向的顶点的路径长设为2,同样可以肯定,只有被路径长为1的顶点所指向的顶点的路径长为2。不过此时会遇到一个问题:v3是v4所指向的顶点,但v3的路径长显然不应该被设为2。所以我们需要对已知路径长的顶点设一个“已知”标记,已知的顶点不再更改其路径长,具体做法在给出代码时将写明。本例中,路径长要被设为2的顶点是v2、v5、v6:

    然后我们继续这样的步骤,将路径长为2的顶点所指向的顶点的路径长设为3。不过本例中路径长为2的顶点所指向的顶点中已经没有未知顶点了,所以算法结束。

    上述步骤随着图的规模变大而变多,但不难发现其规律就是:将路径长为i的顶点所指向的未知顶点的路径长设为i+1,i从0开始,结束条件即:当前路径长为i的顶点没有指向其它顶点,或所指向的顶点均为已知。

    需要注意的是结束条件的说法,我们并没有要求所有顶点都变为已知,因为确定某顶点为起点后,是有可能存在某个顶点无法由起点出发然后到达的,比如我们的例子中的v0,不存在从v1到v0的路径。

    接下来要做的事情就是用代码实现我们所说的思路,此时我们需要注意是我们并不想在图上直接动手脚,因为图可能还有他用,并且直接在图上动手脚也不方便,因为图中顶点可能并没有用于表示是否已知的域和用于表示从起点到自身的最短路径长的域。

    所以我们的做法是将最短路径的计算结果存于一个线性表中,其结构如下:

    其中“一行”为线性表中的一个元素,每一行的四个单元格就是一个元素中的四个域:顶点、是否已知、与起点最短路径长、最短路径中自身的前一个顶点。

    那么之前计算最短路径的过程用这个表来表示的话,就是下面这样:

    当我们想知道从起点到顶点Y的最短路径时,我们只需要找到Y顶点,查看其distance域即可知道,而想知道整条路径是怎么走的,我们也只要追溯Y的preV直到起点即可知道。下面是输出起点到给定终点的最短路径的一个例子:

    //路径表中的元素定义,我们假设顶点vx即数字x,所以元素没有vertex域

    structpathNode

    {

    boolknown;

    intdistance;

    size_t preV;

    }

    //路径表

    structpathNode pathTable[numVertex];

    void printPath(size_t end,struct node*pathTable)

    {

    size_t preV=pathTable[end].preV;if(pathTable[preV].distance!=0)

    printPath(preV,pathTable);elseprintf("%d",preV);

    printf("->");

    printf("%d",end);

    }

    下面是上述无权最短路径思路的一个简单伪代码实现:

    //无权最短路径计算,图存于邻接表graph,结果存入pathTable,起点即start

    void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)

    {

    pathTable[start].known=true;

    pathTable[start].distance=0; //若pathTable[x].distance为0,则其preV是无用的,我们不予理睬//初始化pathTable中的其他元素//curDis即当前距离,我们要做的是令distance==curDis的顶点所指的未知顶点的distance=curDis+1

    for(int curDis=0;curDis

    {for(int i=0;i

    {if(!pathTable[i].known&&pathTable[i].distance==curDis)

    {

    pathTable[i].known=true;//遍历pathTable[i]所指向的顶点X

    {if(!pathTable[X].known)

    {

    pathTable[X].preV=i;

    pathTable[X].distance=curDis+1;

    }

    }

    }

    }

    }

    }

    与上一篇博文的拓扑排序一样,上面的最短路径算法还有改进空间。当我们寻找符合distance==curDis条件的顶点时,我们用的是直接遍历数组的方法,这使得我们的算法时间复杂度达到了O(nv2)(nv为顶点个数),所以我们要改进的就是“寻找符合条件的顶点”的过程。我们可以创建一个队列来存储“需要处理的顶点”,该队列初始时只有起点,当我们修改了某个未知顶点的distance后,我们就将该顶点入队,而当我们令curDis递增后再次寻找distance==curDis的顶点时,我们只需要令队列元素出队即可获取到想要的顶点。这个过程口述难以表达清楚,下面是应该足够清晰了的伪代码:

    //无权最短路径计算,图存于邻接表graph,结果存入pathTable,起点即start

    void unweightedPath(Node* graph,struct pathNode*pathTable,size_t start)

    {//初始化pathTable//创建队列pendingQueue//将起点start入队

    size_t curVertex;while(!empty(pendingQueue))

    {

    curVertex=Dequeue(pendingQueue);

    pathTable[curVertex].known=true;//遍历curVertex指向的顶点X

    {if(!pathTable[X].known)

    {

    pathTable[X].distance=pathTable[curVertex].distance+1;

    pathTable[X].preV=curVertex;

    Enqueue(X,pendingQueue);

    }

    }

    }

    }

    这样一来,我们就将无权最短路径算法的时间复杂度由O(nv2)降低到了O(nv+ne)(ne即边的条数)。此外,上述算法对于无向有圈图也是一样生效的,原因就不赘述了,道理是简单的。

    接下来的问题是如何对有权图进行单源最短路径的寻找。有权图的最短路径显然比无权图要难找,原因在于我们不能套用无权算法的思路,直接令已知顶点所指未知顶点的distance=curDis+weight(weight即两顶点间路径的权重,此处简写),以下图为例:

    若我们令v0作为起点,然后令v0所指的未知顶点的distance=v0.distance+weight,那么v3的distance就会变成5,可是实际上v3的distance应改为2。

    解决的思路是:我们罗列出所有已知顶点指向的所有未知顶点,看这些未知顶点中谁的distance被修改后会是最小的,最小的那个我们就修改其distance,并认为它已知。

    以上图为例,我们一步步走一遍来加深一下理解:

    首先是正常的初始化(我们将边的权重也标识出来),假设起点为v0:

    接着我们罗列出所有已知顶点(只有v0)指向的所有未知顶点:v1、v2、v3。然后发现若修改它们的distance,则v1.distance=v0.distance+1=1,v2.distance=v0.distance+3=3,v3.distance=v0.distance+5=5。显然v1被修改后的distance是未知顶点中最小的,所以我们只修改v1的distance,并将v1设为已知,v2、v3不动:

    接着我们继续罗列出所有已知顶点(v0、v1)指向的所有未知顶点:v2、v3、v4。然后发现若修改它们的distance,则v2.distance=v0.distance+3=3,v4.distance=v1.distance+1=2,v3.distance=v1.distance+1=2(虽然v0也指向v3,但是通过v0到v3的路径长大于从v1到v3,所以v3的distance取其小者),其中v3和v4的新distance并列最小,我们任选其一比如v4,然后只修改v4的distance,并将v4设为已知,其它不动:

    继续,我们罗列出所有已知顶点(v0、v1、v4)指向的所有未知顶点:v2、v3、v6,发现若修改,则v2.distance=3,v3.distance=2,v6.distance=3,所以我们只修改v3的distance,并将v3设为已知:

    继续,我们罗列出所有已知顶点(v0、v1、v3、v4)指向的所有未知顶点:v2、v5、v6,发现若修改,则v2.distance=3,v5.distance=10,v6.distance=3,我们在v2和v6中任选一个如v2,只修改v2.distance,并将v2设为已知:

    继续,我们罗列出所有已知顶点指向的所有未知顶点:v5、v6,发现若修改,则v5.distance=5,v6.distance=3,所以我们只修改v6:

    最后,罗列出的未知顶点只有v5,若修改,其distance=5,我们将其修改并设为已知,算法结束:

    其实上述算法的核心部分就是:

    1.找到所有已知顶点

    2.将所有已知顶点指向的所有未知顶点罗列出来

    3.计算这些未知顶点的最小distance,然后再确定其中新distance最小的顶点X

    4.只修改X的distance,并将X设为已知

    5.回到第二步,若所有已知顶点都没有指向未知顶点,则结束

    而这个算法就是Dijkstra算法的雏形。

    Dijkstra算法核心部分简化的说法就是:找到所有可确定distance的未知顶点中新distance最小的那个,修改它并将它设为已知。

    用伪代码描述就是这样:

    //有权最短路径计算,图存于邻接表graph,结果存入pathTable,起点即start

    void weightedPath(Node* graph,struct pathNode*pathTable,size_t start)

    {//初始化pathNode数组

    size_t curV;while(true)

    {//找到可确定distance的未知顶点中新distance最小的那个,存入curV,若没有则跳出循环//令pathNode[curV].distance和pathNode[curV].prev修改为正确的值

    pathNode[curV].known=true;

    }

    }

    可以确定的是,Dijkstra算法也可以应用于无权图,只要给无权图中的每条边加个值为1的权重即可。并且如果你将无权算法与Dijkstra算法进行对比,就会发现那个无权算法其实就是Dijkstra算法的“特例”,在无权算法中,我们之所以不需要去找“distance最小的未知顶点”,是因为我们可以肯定已知顶点所指向的未知顶点就是“distance最小的未知顶点”。

    不用想都知道,Dijkstra算法中的循环中的两行伪代码其实意味着大量的操作:找到可以确定distance的未知顶点,计算它们的distance,比较出最小的那个,修改……

    显然,Dijkstra算法的核心部分是可以改进的,改进的思路与无权算法也很相像,即“加快寻找符合条件的顶点的过程”。其中一种改进方式是计算出未知顶点的新distance后,将{未知顶点,新distance}对插入到以distance为关键字的优先队列中,而不是直接抛弃非最小distance的那些未知顶点(这是一个很大的浪费)。这样在下一次寻找“distance最小的未知顶点”时,我们可以通过优先队列的出队来获得,从而避免了遍历整个数组来寻找目标的情况。这个想法要细化实现的话,还有不少坑要避开,不过我写到这儿时深感表达之困难与疲惫,所以这篇博文就此打住,如果博文中有什么不对之处,可以在评论区指出,谢谢~

    附:如果有权图中存在权重为负值的情况,则计算单源最短路径将会更加困难,不过可以确定的是,如果有权图中存在圈与负权边,且负权边在圈中,使得圈的路径长为负,那么单源最短路径的计算是无法进行的,因为你可以在这个圈中永远走下去来使路径长不断“减小”。解决有负值权重边的图的最短路径算法是在Dijkstra的算法上进行改进得来的,本文不予讲解(或许以后会有一篇文章介绍),有兴趣的可以自行搜索。

    展开全文
  • 下面小编整理了2022考研计算机考点:带权图的最短路径算法及应用,供大家参考。迪杰斯特拉(Dijkstra)算法求单源最短路径,算法思想:设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作...

    计算机的竞争度逐年加大,报考学生越来越多,对于打算报考2022考研计算机的考生们来说复习是难点,大家复习也需要讲究方法,掌握一定的技巧。下面小编整理了2022考研计算机考点:带权图的最短路径算法及应用,供大家参考。

    迪杰斯特拉(Dijkstra)算法求单源最短路径,算法思想:

    设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。

    1.初始化:初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空。

    2.重复以下工作,按路径长度递增次序产生各顶点最短路径,在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。

    注意:①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。

    (注:本文来自网络 ,如有侵权,请联系删除)

    展开全文
  • 定义:迪克斯特拉算法,是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,...

    Dijkstra算法

    定义:迪克斯特拉算法,是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法
    同时这个有权图中不能出现负边。

    这里解决单源最短路径问题需要先了解Dijkstra算法,所以这里先把个人对于这个算法的理解附上,再解决最短路问题。

    在这里插入图片描述
    以这个图为例,从1号走到7号的最短路径明显是从1到4再到7,这条路径的权值最小。从代码角度就要利用Dijkstra算法来解释。
    在这里插入图片描述
    因为是从1号开始走,所以把所有与1号直接相连点,都记录下来,从1无法直接走到的点,其权值都暂时标记为无穷大。这时发现能走的点当中,权值最小的路径是走到2号,这个时候就走到2号,并把2号标记为走过。
    在这里插入图片描述
    这个时候,再检索,与1号和2号直接相连的所有点,不是直接相连的的权值暂时都记为无穷。这是5号、3号、4号都是直接相连的,走到这些点的对应权值总和是4、2、3。这里说一下5这个点,到5号权值之所以是4,是因为把2号当成中转站了,也就是1->2->5这么走的。 这里又开始选权值最小的路径,那当然是选1->3这条路,走到3号并把3号标记为走过。
    在这里插入图片描述
    把2号和3号当成中转站,开始检索与1、2、3号直接相连的点,并选出权值最小的路径、并刷新到每个点的权值,(无法直接到点,到那个点的路径权值暂时标记为无穷,意味着暂时走不到) 到5、6、3号的路径权值分别为4、8、3,所以到4号。
    在这里插入图片描述
    来到4号,再重复上述操作,到5、6、7的路径权值分别为4、8、7。所以选7号,走过去。
    在这里插入图片描述
    此时,已经到了目标点7号。但是,所有的点还没走完,所以接着走。
    到了这里相信大家都知道该怎么做了,就是照着葫芦画瓢,把走过的路径当成中转站,检索所有可以直接走过去的点、计算出到那个点的权值、选出路径权值最小的一条,去走。最后又开始,调整到每个点的路径权值(因为走了一个点,就又多了一个中转站)
    在这里插入图片描述
    最后,图会呈现这样的状态,而到每个点的路径权值都计算出来了,也记录了到每个点的路径最小权值。
    总结一下就是,先检索每个能直接相连的点 (与中转站相连也算直接相连) ,并选出路径权值最小的那个点,走过去,标记那个点走过了,接着把那个点当成中转站,调整一下到每个点的路径权值,无法直接走到的点的路径权值就记为无穷大(意思就是暂时还走不到那个点),如此反复,直到所有点都走过了为止。
    因为每次选的都是路径权值最小的,所以到目标点的路径权值一定是最小的。
    这里把走过的点当成中转站,是一种理解,也可以把走过的点看成一个整体,当成一个大的点,也可以当成把那个点吞了之类的,怎么好想怎么来吧。

    图结构练习——最短路径

    Description
    给定一个带权无向图,求节点1到节点n的最短路径。
    Input
    输入包含多组数据,格式如下。
    第一行包括两个整数n m,代表节点个数和边的个数。(n<=100)
    剩下m行每行3个正整数a b c,代表节点a和节点b之间有一条边,权值为c。
    Output
    每组输出占一行,仅输出从1到n的最短路径权值。(保证最短路径存在)
    Sample
    Input

    3 2
    1 2 1
    1 3 1
    1 0
    Output
    1
    0

    #include<bits/stdc++.h>
    #include<string.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    int mp[111][111]; //图 
    bool vis[111]; //标记是否走过 
    int point[111]; //用来到某个点需要的权值 
    void dijkstra(int n)
    {
    	int i,j,k,min,u;
    	for(i=1;i<=n;i++) //因为是从1开始 
    	{
    		point[i]=mp[1][i];//先把与1相连的所有的点的权值,都记录下来 
    	}                       //不相连的那些点记录进去的是无穷,但不影响后面的判断,因为是找最小的,所以无穷不影响判断 
    	vis[1]=1; //1点标记为走过了 
    	for(i=1;i<n;i++)//进行n-1次查询 
    	{
    		min=inf;
    		for(j=1;j<=n;j++)
    		{
    			if(min>point[j]&&!vis[j]) //那个点没被走过的情况下,开始找最小的权值,并把那个点记录下来 
    			{
    				min=point[j];
    				u=j;
    			}
    		}
    		vis[u]=1;//找到的那个点,标记走过了 
    		for(k=1;k<=n;k++) //开始调整到n个点的权值 
    		{
    			if(!vis[k]&&mp[u][k]<inf&&point[k]>mp[u][k]+point[u]) //在那个点没被走的情况下,从当前点能走到那个点的情况(废话,能走才会走过去) 
    			{                                                //把当前记录的权值,与加入新点后走到那个点所需要的权值进行比较,记录小的那个 
    				point[k]=mp[u][k]+point[u];
    			}
    		}
    	}
    	printf("%d\n",point[n]); //最后输出走到n点需要的总权值 
     } 
     int main()
     {
     	int n,m;
     	while(~scanf("%d%d",&n,&m))
     	{
     		memset(vis,0,sizeof(vis));//初始化 
     		memset(mp,inf,sizeof(mp)); //先把图中到所有点的步数都记为无穷 
     		memset(point,inf,sizeof(point));
     		for(int i=1;i<=n;i++) //当前点到当前点的步数记为0 
     		{
     			mp[i][i]=0;
    		}
    		while(m--)//开始读入图 
    		{
    			int x,y,z;
    			scanf("%d%d%d",&x,&y,&z);
    			if(mp[x][y]>z)//这里是为了防止路径覆盖 
    			{            //比如说同一条路重复了2次但是路径数不一样,那肯定是记录小的那个 
    				mp[x][y]=mp[y][x]=z;
    			}
    		}
    		dijkstra(n); //把终点传过去 
    	 }
    	 return 0;
     }
    

    这里的代码也是参考了学校里的学长和csdn的大佬。
    如果你有任何建议或者批评和补充,请留言指出,不胜感激。

    展开全文
  • 问题描述:用狄斯奎诺算法求解如图所示的单源最短路径问题
  • 二叉树最短路径

    2021-04-06 08:21:25
    建立城市道路网络模型及其数据库 , 应用一种改进的 Dijkst ra 算法对城市道路进行最短路径查询 , 该算法是从起点和终点分别用二叉树按起点到终点 和终点到起点的......本文提出的双向 Dijkstra 二叉树算法就是为解 ...
  • C语言最短路径问题

    2021-05-20 14:05:38
    //记录最短路径。。 int MOVE[9][3] = {2, 2, 2, 2,-1, 0, 2,-1, 1, 2, 0, 1, 2, 1, 1, 2, 1, 0, 2, 1,-1, 2, 0,-1, 2,-1,-1}; int i; int j; printf("请输入迷宫的大小:\nm="); scanf("%d", &m); printf("n="); ...
  • 这里写目录标题图图的表示结论:图的导航-最短路径算法A*算法 图 在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就 是这些圆圈之间的连线。顶点之间通过边连接...
  • C++解决最短路径问题

    2021-11-10 10:47:21
    先说多源最短路径算法 1.floyd算法(暴力n3): 核心代码只有三行,文字描述就是:假设n个点,点与点间有m条边(无独立的点),我们要求每个点到到其他n-1个点的最短路径,首先就是用邻接矩阵进行存图,初始化INF...
  • matlab网络最短路径

    2021-04-18 12:04:08
    2.3 用 matlab 程序实现上述算法编写程序...C OLUMNS 特别企划 基于遗传算法的最短路径问题及其 MATLAB实现文/张书源 郭聪 前言在现实生活中,我们经常遇到最 短路问题,例如寻找两点之间总长度最 短或者费用最低的...
  • 如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0,0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。示例 1:输入:grid =[[0,0,0],[...
  • 一,概念单源最短路径给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为...
  • 动态规划之最短路径

    千次阅读 2020-12-20 13:20:33
    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下...昨天做了道算法,感觉画图很有助于自己理解算法的过程,这次再挑一个算法加深印象。碰到这种类型的题目,和递归很像,但是使用递归,如果数据范围...
  • 一:最短路径问题(一)定义在...有向,无向从某固定源点触发,求其到所有其他顶点的最短路径多源最短路径求任意两顶点间的最短路径可以通过对每个顶点使用一次单源(不是最好)二:无权图的单源最短路径(有向)不考虑...
  • 《(最新整理)排列组合第3阶表格最短路径问题08》由会员分享,可在线阅读,更多相关《(最新整理)排列组合第3阶表格最短路径问题08(4页珍藏版)》请在人人文库网上搜索。1、完整)排列组合第3阶表格最短路径问题08(完整)...
  • 1、最短路径问题单源多源、有权无权单源:固定起点,计算到其他每个顶点的最短路径,又分无权图 && 有权图多源2、无权图的单源最短路算法1)思想:路径长度为0的:起点路径长度为1的:……路径长度为2的:...
  • 最短路径问题 当我们通过网络浏览网页,发送电子邮件、QQ消息传输的时候,数据在互联网设备之间流动 计算机网络专业领域会详尽地研究网络各层面上的技术细节 我们对Internet工作方式感兴趣的主要是其中包含的图算法...
  • 湖北大学本科毕业论文(设计)PAGEPAGE IIl湖 北 大 学本 科 毕 业 论 文 (设 计)最短路径算法及其应用姓 名 学 号专业年级指导教师 职 称年 4月 20 日湖北大学本科毕业论文(设计)PAGE I目 录绪论………………...
  • 最短路径 最短路径的求取有两种经典的算法,分别是Dijkstra算法和Floyd算法 这Dijkstra算法的算法思想是基于贪心算法的,也就是选择权值最小的边 而Floyd算法的算法思想是根据动态规划,不断迭代取得的 Dijkstra算法...
  • 蚁群算法最短路径java

    2021-03-16 11:36:44
    改进蚁群算法求解最短路径问题 袁亚博,刘羿,吴斌 【摘要】摘要:针对蚁群算法在求解最短路径问题时存在容易陷入局部最优 解的问题,对经典蚁群算法提出三方面改进。...网络出版时间:2016-11-21 16:41:28 网络出版地址:...
  • 数据结构课的实验题目,涉及到LCA问题,这次暴力解决了,以后学了NB算法回来做个...编程任务:对于给定的二叉树,和二叉树中结点对,编程计算结点对之间的最短路径。数据输入:由文件input.txt给出输入数据。第1行有1...
  • 图算法(二) 最短路经 Shortest Path Dijkstra算法练习链接 /vjudge/contest/view.action?cid=29337#overview Floyd算法练习链接 /vjudge/contest/view.action?cid=29305#overview 密码都是:671 /sjjg/...
  • 查找有向图最短路径

    2021-03-01 07:58:13
    老师有一个:使用狄克斯屈拉(Dikjstra)标号算法可得出解:我用Java来实现了一下这个算法:package test;import java.util.ArrayList;import java.util.Arrays;import java.util.HashSet;import java.util.List;import...
  • 单源最短路径,关于这个问题的贪心算有点不好理解,分析后续补充,代码也需要后续优化,便于理解package test;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/*...
  • 第八十五天 --- 图论最短路径专题(力扣743、5888)题目一朴素Dijkstra解决无负权边的单源最短路径问题思路代码邻接矩阵邻接表复杂度Floyd解决多源点最短路径问题题目二堆优化Dijkstra解决无负权边的单源最短路径...
  • 最短路径问题(更新)

    千次阅读 2021-05-12 13:56:18
    转载自:最短路径问题 问题介绍 简单地说,就是给定一组点,给定每个点间的距离,求出点之间的最短路径。 路径问题大概有以下几种: 确定起点的最短路径问题:已知起始点,求起点到其他任意点最短路径的问题。...
  • 该算法由著名计算机科学家Edsger Wybe Dijkstra提出,使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题。该算法至今在各类地图等商业环境被广泛使用,是知名度非常高的算法之一。该算法的核心是贪心...
  • 题目链接:P4779 【模板】单源最短路径(标准版) 给定一个 n个点,m 条有向边的带非负权图,请你计算从 s 出发到每个点的距离。 数据保证你能从 s 出发到任意点。 输入格式 第一行为三个正整数 n,m,s 第二行起 m行...
  • 算法:广度优先搜索(BFS)(最短路径)算法:广度优先搜索(BFS)(最短路径)我们先看一个案例:遍历一个树结构,按层次输出树的节点内容,即:欲求 A B C D E F。实现方式便是从根节点(A)向下遍历,先获取A,其次是A的子...
  • 最短路径问题是:给定图G(V,E),求一条从起点到终点的路径,使得这条路径上经过的所有边的边权之和最小。 对任意给出的图G(V,E)和起点S、终点T,如何求从S到T的最短路径。解决最短路径问题的常用算法有Dijkstra算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,408
精华内容 21,363
关键字:

最短路径的题