使用dijkstra算法在图中寻找源和目的地之间的最短路径
Dijkstra算法是一种用于在图中寻找源节点和目标节点之间最短路径的经典算法。它是一种贪心算法，通过逐步选择当前最短路径的节点来逐步扩展最短路径，直到找到目标节点或者遍历完所有节点。
Dijkstra算法的基本思想是维护一个距离表，记录从源节点到各个节点的当前最短距离。算法开始时，将源节点的距离设置为0，其他节点的距离设置为无穷大。然后，从距离表中选择当前距离最小的节点，将其标记为已访问，并更新与该节点相邻的节点的距离。如果通过当前节点到达相邻节点的路径比已记录的最短路径更短，则更新距离表中相邻节点的距离。重复这个过程，直到找到目标节点或者所有节点都被访问。
Dijkstra算法的优势在于能够找到源节点到目标节点的最短路径，并且对于有向图和无向图都适用。它在很多实际应用中都有广泛的应用，比如路由算法、网络优化、地图导航等。
在腾讯云中，可以使用腾讯云的图数据库TGraph来支持Dijkstra算法的实现。TGraph是一种高性能、高可靠的分布式图数据库，提供了丰富的图计算算法和API接口，包括Dijkstra算法。通过TGraph，可以方便地构建和管理图数据，并使用Dijkstra算法来进行最短路径的计算。
腾讯云TGraph产品介绍链接：https://cloud.tencent.com/product/tgraph
请注意，以上答案仅供参考，具体的技术选型和产品选择应根据实际需求和情况进行评估和决策。
相关·内容
1回答
是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。
以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了
Dijkstra的算法22用于计算N个阶段的最短路径(步骤5)。考虑N= 2，在第一阶段，Dijkstra算法确定了两个网络设备之间最短的路由，从而使所有链路开销的权重增加了10倍。紧接着，在第二阶段(并且随着链路成本的增加)，Dijkst
浏览 0提问于2015-11-25得票数 2
回答已采纳
我想写一个算法，在有向图和无向图中找到两个特定顶点-源和目标-之间的最短路径。
我知道dijkstra的算法，它用来寻找所有的最短路径图。但是，您是否会修改此算法以仅查找两个顶点之间的最短路径？
浏览 31提问于2018-01-11得票数 0
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
4回答
“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别，哪种算法是图中最短路径的最佳选择？
我需要计算网络中所有对之间的最短路径，并将结果保存到一个数组中，如下所示：
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
浏览 20提问于2009-12-04得票数 27
回答已采纳
我的图不包含将顶点连接到自身的边。两个顶点之间只有一条边。从上我了解到了一些根据给定条件计算最短路径的算法。最著名的算法之一是Dijkstra's algorithm算法，它寻找从源顶点到图中所有其他顶点的最短路径。
但是通过使用Dijkstra's algorithm，我不需要探索所有的顶点，然而我的目标只是找到从单个源到单个目的地的最短路径。我应该在这里使用哪种策略？这样我就不需要探索所有其他的顶点了。
我的一种方法是使用bidirectional bfs。我所说的bidirectional bfs是指应用两个bfs，一个来自source node，另一个来自destina
浏览 0提问于2012-04-07得票数 2
回答已采纳
我正在寻找一种有效的方法来遍历一个包含多个源顶点和多个目标顶点的大图。具体来说，如果存在这样的路径，我希望为每个(源、目标)对找到最短路径。显然，这可以通过对每个源点的宽度优先搜索来完成，但是考虑到图中的许多路径将被多次遍历，我想会有一个更短的方法。
下列事实可能与此相关：
图是有向的，并且非常稀疏。它有一些循环。对于绝大多数(源、目的地)对，将不存在路径。My图是在C++中实现的，它是具有指向父节点和子节点的节点(双向遍历是可能的)。边沿上有重量。--
浏览 2提问于2019-10-07得票数 2
2回答
今天我遇到了这个词“单对最短路径问题”。我想知道对加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想，如果你想找到A和Z之间的最短路径，你绝对必须知道从A到B，C，D，……的最短路径。Y.
如果你不知道后者，你就无法确定你的道路实际上是最短的。因此，对于我来说，任何最短路径算法都必须计算出图中从A到其他顶点的最短路径，才能得到从A到Z的最短路径。
这是正确的吗？
如果是的话，有研究报告证明这一点吗？
浏览 4提问于2017-03-30得票数 10
回答已采纳
2回答
我正在做一项任务，它让我遍历一个简单的正方形图，目的是积累最少的危险。终点很简单:从左上角到右下角。我只限于水平和垂直移动之间的顶点。地牢里的每个房间(图上的每个顶点)都有一个特定的危险等级。
示例：
0 7 2 5 4 0 -> 1 -> 1 -> 2 -> 2 -> 1 -> 3 -> 1 -> 0
1 5 1 2 1
1 2 2 1 1
1 9 5 3 5
1 1 9 1 0
我一直在抛出使用优先级队列的想法，但我仍然不知道如何，确切地说，我会在第一时间使用那个P。
我可以尝试Dijkstra的算法，但我不是计算节点之间的距离，而是
浏览 0提问于2015-05-12得票数 1
回答已采纳
我正在寻找关于从哪里开始寻找解决这个问题的方法的指点。
在谷歌搜索了一段时间之后，我发现的唯一问题就是一个。区别在于，我不是在寻找一棵树，它跨越了图中的所有顶点，而是谁跨越了给定的3个顶点。
我不是在寻找一个完整的程序，而是一个指向总体方向的答案。
我的另一个想法是使用运行3次搜索。这个想法是通过组合不同的最短路径来找到最好的路径。我不知道如何做到这一点。
下面是我所讨论的图形类型的一个图形示例：
因此，我们的任务是找到一种方法，在这类图中找到连接任意三个顶点的最小和权。
编辑:
我用Dijkstra的算法进行了3次搜索，解决了这个问题。然后，通过添加所有的单边，找到了连接三个顶点的
浏览 11提问于2013-12-27得票数 2
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
2回答
给定一个加权无向图，需要找到两个节点之间的最短路径，这实际上是一个经典的最短路径问题。但是还有一个约束:每个节点都包含一个“约简”值，可以用来降低一个遍历的下列边的成本(不仅是相邻的，而且约简也不是累积的)。因此，您可以使用您之前所经历过的一个节点中的“约简”来降低边缘的成本(每个边的最终成本不能小于0)。
请注意，一旦我们通过一个节点的缩减，我们可以再次使用它的所有以下边缘(不只是相邻的，它是可以无限的时间)。减少不会累积。
让我们考虑一下这张图：
在此图中，从节点1到节点5的最短路径是：
1 -> 4，费用13 (15-2)
4 -> 3，费用为0 (12-1
浏览 0提问于2018-02-17得票数 2
回答已采纳
1回答
问题是如何从起始顶点到directed graph中的所有其他顶点寻找最短路径。
但是图有m positive加权边和k negative加权边，并且保证了负加权边不会在一个循环中。换句话说，在这个图中没有负的加权循环。
我试图直接使用Bellman-Ford和SPFA来解决这个问题，但是有没有更快的方法来解决这个问题呢？
浏览 4提问于2020-12-16得票数 3
回答已采纳
1回答
我正在寻找双向搜索的实现(也就是。对于Java中的Dijkstra (或任何其他源到目的地的最短路径算法)，可以使用“中间相遇”算法。
由于双向搜索处理比看起来更复杂()，我想在重新发明轮子之前考虑一下现有的实现！
附言:我说的是，不要与双向图混淆)
下面是一个棘手的图表示例：
浏览 3提问于2012-05-28得票数 9
回答已采纳
因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。
问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B；C，K的最短路感兴趣，我们可能只需要一次就能找到两条路吗？
浏览 2提问于2018-03-12得票数 1
1回答
我目前的理解是，dijkstra的算法比贝尔曼-福特算法更有效，只是它不能处理负边缘。然而，假设我们有一个边权重图，其中有负权重的边，图中没有负权重的圈，我们还能使用dijkstra算法吗？
浏览 7提问于2019-11-28得票数 2
给定:无向加权连通图。s，t是顶点。
问题:找到一种尽可能高效的算法，从s到t返回路径。在该路径中，具有最高权重的边缘将具有尽可能少的权重。因此，如果我们从s，t有5条路径，对于每条路径，我们都有最重的边，所以这5的最小边。
我试过的是：
使用的一些算法来寻找s和t之间的最短路径。
删除所有不是我们找到的最短路径的一部分的边
使用BFS进行一些修改后，我们根据从s到t的路径数来运行BFS，每次我们找到最大边缘并将其存储在数组中时，我们就会找到数组的最小值。
我很难找到一种可以在(1)中运行的算法，Bellman ford将无法工作--因为它必须是有向图。Dijkstra不能
浏览 6提问于2017-08-02得票数 3
4回答
寻找图中两点之间的最短路径是一个经典的算法问题，有许多好的答案(，等)。我的问题是，是否有一种有效的算法，在给定一个有向加权图、一对节点s和t以及一个值k的情况下，找到s和t之间的第k条最短路径。如果有多条相同长度的路径都与第k条最短路径相同，则算法可以返回其中任何一条路径。
我怀疑这个算法可能可以在多项式时间内完成，尽管我知道可能会减少，这将使其成为NP困难。
有没有人知道这样一种算法，或者说有一种约简表明它是NP-难的？
浏览 1提问于2011-08-27得票数 28
回答已采纳
1回答
我有6个城市在我的记录里。孟买，blore，Hbad，德里，chennai，pune。并记录每个城市的特色菜。
当用户出现在我的页面上时，我想显示基于位置相关性的记录。我想用最短的距离。
从用户的IP，我可以得到他的位置(城市或朗拉蒂)。我想要计算用户与上述每一个城市的距离。这是最近的，我应该选择它来显示记录。
有什么更好的方法吗？我正在使用php。
请在执行层面上谈谈..。
浏览 1提问于2014-01-25得票数 1
回答已采纳
4回答
我在试着解决一个图形问题。图是有权的和无向的。
图形大小：
no. of vertices upto 200,000
no. of edges upto 200,000
我必须找到图中给定的2个节点(S & D)之间的最短路径。我正在使用Dijkstra's algorithm来查找这个。
现在的问题是图是频繁变化的。如果从图中删除特定的边，我必须找到S和D之间的最短路径。我正在使用Dijkstra的算法重新计算新的路径，将图视为边删除后的新图。然而，这种方法太慢了，因为可能有200,000条边，每次删除边我都要计算200,000次最短路径。
我在考虑使用任何记忆技术，
浏览 1提问于2012-06-18得票数 5
1回答
假设我有一个源节点S、目标节点D和由中间节点P1、P2、P3、…组成的集合A边加权无向图中的。我想找到顶点Pi∈A 最小化dist(S，Pi)+dist(D，Pi)？此外，从S到D的总体路径应该只包含一个从集合A到集合A的节点。我不想用蛮力的方法。
浏览 0提问于2014-04-09得票数 1
我正在为一个基于网格的自上而下的游戏做A*寻路。我遇到的问题在下图中可能是最容易理解的。星号是播放器/NPCs。黄色星号是当前想要到达X的NPC。红色星号是NPC，在这种情况下是障碍。黄色细胞是墙壁，白色细胞是地板。虽然通向目标的整个路径确实无法到达，但我仍然希望获得一条通往下一个最佳位置的路径(在本例中，spot编号为8)。
我可以很容易地让它绕过障碍物，但不确定如何完全按照我所描述的那样做。如果我在遇到障碍物时停止它，它在3停止时就不能正常执行。如果我重走封闭列表中离最终目标距离最小的磁贴，例如最终目标在墙的另一边，它也会把事情搞得一团糟。
有什么建议吗？我觉得我遗漏了一些很明显的东西，所
浏览 2提问于2012-10-25得票数 5
回答已采纳
3回答
我很难理解的用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢，但我想不出来。根据维基百科，Johnson算法使用Bellman Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法查找最短路径。但贝尔曼·福特算法也是一种寻找最短路径的算法。为什么我们不使用从贝尔曼·福特算法得到的最短路径呢？
浏览 0提问于2011-03-16得票数 4
回答已采纳
我读到了有关图算法的文章，我发现了这两种算法：
Dijkstra算法和BFS算法在寻找节点间最短路径时有什么区别？
我找了很多关于这件事，但没有得到满意的答案！
在图中查找最短路径的BFS规则如下：
我们发现所有连通的顶点，
将它们添加到队列中，并且
存储从源u到顶点v的距离(重量/长度)。
更新的路径从源u到那个顶点v的最短距离，我们有它！
这正是我们在Dijkstra算法中所做的事情！
那么，，为什么这些算法的时间复杂度如此不同？
如果有人能用伪代码来解释它，我会非常感激的！
我知道我错过了什么！请帮帮我！
浏览 8提问于2014-08-22得票数 65
回答已采纳
1回答
我最近开始使用SDN和泛光灯控制器。我想通过删除现有的路由算法(Dijkstra算法)来改变泛光灯中的路由算法，有链接吗？
浏览 9提问于2019-12-15得票数 2
回答已采纳
嗨，我在为这个问题而挣扎。其内容如下：
设计一种算法，在加权有向图G= (V，E)中求最小权环(即图中所有圈的最小边权和)。简要说明运行时和空间的复杂性。假设所有的边都是非负的。它应该在O时间内运行。提示:对Dijkstra的算法使用多次调用。
我已经看到了使用弗洛伊德-沃尔的解决方案，但我想知道我们将如何使用Dijkstra，以及如何在给定的时间限制内做到这一点。
我有几点困惑：
首先，我们如何知道图中有多少圈，以及如何检查这些循环？
还有，为什么会是E_？根据我的理解，你应该遍历所有的顶点，因此使它成为？
这是为了我的个人学习，所以，如果任何人有他们可以使用的例子，
浏览 4提问于2017-11-26得票数 0
1回答
我正在做一个在图中寻找最短路径的项目，并且我必须能够指定开始和结束顶点。我已经使用Boost完成了大部分工作，但我还剩下一个问题。如何指定起始顶点？这是我的代码。如果您能为我指明正确的方向，我将不胜感激。有问题的那一行是所有**的那一行，靠近底部。
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#includ
浏览 2提问于2013-12-16得票数 0
在“算法入门，第三版”练习24.3-5中，需要一个例子说明这是错误的(并不总是正确的)。这有可能吗？在我看来，这是不可能的，因为在通往当前停战的道路已经决定的时候，每个边缘都是放松的。
逐字逐句地：
教授N.声称有Dijkstra算法正确性的证明。他声称Dijkstra的算法按照图中每条最短路径在路径上出现的顺序来松弛它们的边，因此路径松弛特性适用于每个可从源到达的顶点。显示教授错误地构造了一个有向图，而Dijkstra的算法可以放宽最短路径的边。。
浏览 6提问于2010-09-18得票数 13
回答已采纳
1回答
我知道A*是寻找最短路径的最优算法，但我不知道任何启发式算法是如何在非格图上工作的？这让我想知道A*实际上是否能够用于无向或有向图。如果A*能够做到这一点，那么什么样的启发式方法可以使用呢？如果A*不是，那么目前在有向或无向非格图上计算最短路径的最快算法是什么？如果需要更多的信息，请发表评论。
浏览 0提问于2014-12-08得票数 2
回答已采纳
3回答
有向图G(V，E)有权函数w，所以每个(u，v)的权都是正值。我需要找到图中最轻量级的圆，顶点k‘是其中的一部分。
我还给出了一个我可以使用的算法，它可以为具有正权值的图找到最轻量级的路径(我只能使用它一次)。
我考虑创建一个子图G‘，其中所有的顶点和边都是强连通的分量。找出k‘是其中一部分的图。然后找出从k‘到某些顶点v的最轻量级的相邻边。从该v中，我可以运行给定的算法并找到轻量级路径，然后添加丢失的顶点的权重( (k'，v) )。
看上去是对的吗？我刚开始上这门课，我觉得我还没到那里。
浏览 3提问于2017-11-21得票数 0
回答已采纳
我试图用优先级队列实现Dijkstra的算法。
据我理解，“Dijkstra的算法”允许找到最短的‘路径’，因为它将返回一个构成最短路径 *的顶点集。
从这里的答案来看，，以及()，我应该能够使用两种数据结构来实现它:一个图形和队列数据结构。
但是，在我使用上述两个数据结构实现时，当我最终到达目标节点时，我没有存储顶点路径？换句话说，我只有最短的distance (一个标量值)。
这是什么意思呢？我唯一能想到的方法是使用，一个额外的数据结构--一个数组或哈希映射，其中key将是顶点，value将是它的父级。
的实际问题：
是否需要额外的数据结构(“构成最短路径的顶点集 *")？如果
浏览 0提问于2019-06-15得票数 2
我正在寻找一种算法来找到两个URL之间的最短路径，或两个维基百科页面。
例如，从Reddit的维基百科文章到计算机科学文章的最短方法是沿着科学的链接，那里有一个到计算机科学的链接。
假设所有链接都是静态的，加载整个图或遍历整个图都是不切实际的，有没有实用的算法来找到最短路径，或者证明不存在路径？
(我不确定Dijkstra的是不是这里的最佳选择，因为图中每条边的权重是1)
浏览 7提问于2009-11-07得票数 4
我在这个问题上已经困了两天了，至今仍未取得任何进展。基本上问题是这样的:给定一个无向简单加权连通图，在访问给定集合的至少一个顶点时，我们必须找到从给定源到给定目的地的最短步行，同时访问集合B中的至少一个顶点，附加的约束条件是，集合B的顶点应该总是在访问集合A的顶点之后才能到达，而且图中可能存在既不属于A也不属于B的顶点。
我试着把最短的路径分解成一个访问顶点的路径，从A到B，从v到另一个，然后从w到目的地。这可以分别使用不同起始点的Dijkstra 3道次进行。但是，我必须选择这样的最小v，从而导致O(V_E_log(V))复杂度，其中V=顶点数，E=边数。我对如何在O(E*log(V))中这
浏览 2提问于2020-06-07得票数 1
回答已采纳
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
我知道这两个算法用来解决不同的问题，dijkstra算法是用来在图中寻找最短路径，而kruskal算法是用来寻找graph.But的最短路径，它们是如此相似？它们之间是什么关系？这两位作者之间是什么关系呢？为什么它们如此相似？
浏览 1提问于2013-06-21得票数 0
回答已采纳
2回答
除了Dijkstra外，还有另外一种方法来计算近似完全图的最短路径吗？我有大约8,000个节点和大约1,800万个边缘。我已经浏览了线程，并决定使用Dijkstra。我用Perl编写了我的脚本，使用的是Boost：：。但结果和我预期的不一样。使用调用$ 10+ ->Dijkstra最短路径($start_node，$end_node)计算一条最短路径花费了大约几分钟的时间；
我知道有很多的边缘，这可能是背后的原因，缓慢的运行时间。我死在水里了吗？还有其他方法来加速这件事吗？
浏览 4提问于2009-09-12得票数 3
2回答
我使用netwrokx计算不同顶点之间的最短路径，使用Dijkstra算法。我有一个例子，我想连接三个不同的顶点(例如，A，B和C在一个无向图中)。首先，我找到了从A到B的最短路径，然后我想要找到从A到B的路径的最短路径。到目前为止，我尝试的是从A到B路径的所有节点到C的最短路径长度，然后计算出从节点到给定最小路径长度的最短路径。这是计算密集型的，因为路径可能有多达200到300个节点。
有人能给我一个提示吗?我如何改进方法？或者更容易找到从已有的边缘到目标的最短路径？
浏览 1提问于2018-08-15得票数 2
回答已采纳
嗨，我正在寻找最好的算法，以找出最优路径遍历有向图和加权图。
大家好，我正在编辑问题，以便完整地解释我的需求
例如:如果在一个有5个节点的图中(让我们分别为所有5个节点分配编号1,2,3,4,5 )，如果我希望从节点2开始遍历，并在4结束，覆盖所有节点，那么哪种算法是解决问题的最佳算法？
我们可以有两个假设：
a)任意两个节点之间总是有一条边。(表示对于两个节点(A和B)，存在从A到B以及从B到A的边。
b)我们可以遍历一个节点两次(如果需要遍历完整的图)。
浏览 0提问于2013-12-06得票数 4
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
1回答
我试图在加权图中求出最短路径
import networkx as nx
import matplotlib.pyplot as plt
g = nx.Graph()
g.add_edge(131,673,weight=673)
g.add_edge(131,201,weight=201)
g.add_edge(673,96,weight=96)
g.add_edge(201,96,weight=96)
nx.draw(g,with_labels=True,with_weight=True)
plt.show()
为了做到这一点，我使用
nx.shortest_path(g,source=13
浏览 24提问于2019-12-15得票数 5
回答已采纳
1回答
我有一个三角形矩阵NxN表示顶点之间的距离(顶点我只与向量j>i连接)，我想从第一个到最后一个对路径进行采样，并使用它作为训练样本。有算法来做吗？在A*中交换min->样品是否足够？
浏览 0提问于2020-01-13得票数 2
1回答
粒子群优化算法
、、、、
在使用PSO算法解决交通问题时，我有一个问题。假设我们有n辆车(仅限于四辆车)，这些车都有相同的目的地。它们有不同的起点城市。(假设我们知道它们的位置(x，y)) D:起点城市和目的地之间的距离。d:它在耗尽汽油之前可以行驶的最大距离。D >> d:每辆车必须加N次油，N=D/d，每辆车应该遵循的路线是不确定的。任务:我们正在寻找最少数量的加油站，这样每辆车都不会抛锚(当然是因为汽油)。有多少个加油站，它们的位置是什么？
浏览 3提问于2015-05-16得票数 0
2回答
假设我有一个带有N顶点和M边的图M。每一条边都有它的长度和时间(例如，以分钟为单位)，通过该边所需的时间。我需要在图中找到顶点1和N之间的最短路径，这是在T分钟时间内执行的。因为时间是更有价值的资源，我们关心的是在时间上遍历图，只有在最短的时间内，我才决定使用Dijkstra的算法，对此我考虑了每条边的时间作为它的权重。我添加了一个向量来存储持续时间。因此，该算法返回最少的时间，而不是最小的长度。一位朋友建议在我的代码中添加以下内容：
int answer(int T) {
int l = 1;
int r = M; // a very big number
int a
浏览 7提问于2021-12-17得票数 0
2回答
我正在寻找一种算法，我肯定已经研究过了，但我对图论还不太熟悉，甚至不知道要搜索的正确术语。
在抽象中，我正在寻找一种算法来确定可达顶点x1、x2、xn和某个起始点之间的路由集，当每条边都有一个权重，而每条路径只能有给定的最大总重量x时。
从更实际的角度来说，我有公路网，每个路段都有一个长度和最大的旅行速度。我需要确定从网络上的任何起点到某一时间范围内可以到达的区域。如果我能找到在这段时间内可以到达的最远点，那么我将使用凸包算法来确定区域(这对我的用例来说已经足够了)。
那么，我的问题是，我如何找到这些终点？我的第一个直觉是使用Dijkstra的算法，并在我“消耗”了一定的“预算”时间后停止，从
浏览 3提问于2015-07-09得票数 3
回答已采纳
1回答
我想弄明白为什么有人更喜欢弗洛伊德-沃夏尔而不是迪克斯特拉：
Dijkstra使用一个可以理解的系统，结合回溯，给出了一个正确的结果。
弗洛伊德-沃夏尔做了一个完整的名单和过滤器在那里。
我唯一能想象的是巨大的图表，在这种情况下，Dijkstra只给出了一个解，结果是给出结果的时间非常长。弗洛伊德-华沙尔，然而，已经开始吐出不同的可能性，并试图一点一滴地改进(例如，基于启发式)。但如果这是真的，那么迪克斯特拉就不会也是这样吗？
还是有其他原因我没有想到这里？
请注意:我正在处理的图是“典型”图，其中车辆需要从一个地方到另一个地方，边的权重等于顶点之间的距离(这是我所走过的点)。边可能是定向的，
浏览 0提问于2023-01-20得票数 1
回答已采纳
我已经读到图中是否存在的问题是NP-完全的，而且由于在多项式时间内运行，所以不能修改它以求最短的哈密顿路径。(这逻辑有效吗？)
但是，如果给出一个无向图上的两个节点(例如A和Z) (所有边都有非负代价)，并且给定的节点(A和Z)至少有一条哈密顿路径作为端点，该怎么办？考虑到这些规范，现在是否有可能修改Dijkstra的算法，以A和Z为端点寻找最短哈密顿路径？(多项式时间)
注意:我只关心从两个节点找到最短哈密顿路径。例如，如果有一个包含26个节点(标记为A到Z)的图，那么通过所有点但从A开始到Z结束的最短路径是什么(我不关心寻找其他具有不同端点的Hamiltonian路径，只有A和Z)
附加问
浏览 16提问于2014-06-25得票数 2
回答已采纳
4回答
首先，让我们定义算法：
Dijkstra算法在具有非负边权的有向图中寻找单源最短路径.
我想知道如何使用Dijkstra算法将最短路径形式s保存到t。
我在谷歌上搜索，但找不到任何特别的东西；我也改变了Dijkstra算法，但我无法得到任何答案。如何使用Dijkstra保存从s到t的最短路径？
我知道我的问题是基本的和不专业的，但任何帮助都将不胜感激。谢谢你考虑我的问题。
浏览 6提问于2015-03-11得票数 11
回答已采纳
2回答
假设有一个图(V，E)是有向和加权的。
图中每条边的权重为1、2或3。
怎样才能快速有效地找到最短的路径呢？提前谢谢！！
浏览 3提问于2020-10-27得票数 2
回答已采纳
2回答
计算边连通性的有效算法？
、、、
我想知道的是，是否有任何文献可以让我阅读算法来确定给定图中所有边的边连通性。
给定边的边连通性(正如我所理解的)是通过给定边的最短路径(在diff节点之间)的数量。也就是说，如果我们从每一个节点移动到另一个节点，我们会经过多少次给定的边。
浏览 2提问于2012-09-30得票数 0
回答已采纳
1回答
首先，让我们定义算法：
Dijkstra算法在具有非负边权的有向图中寻找单源最短路径.
如果我有一个源S和目标T，我可以用Dijkstra算法在这两个顶点之间找到最短路径，但是我想要找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过形式K。
第一部分是Dijkstra算法，第二部分是BFS算法，因为我们可以用BFS算法在无加权图中找到最短路径。
所以我想知道有什么方法可以改变dijkstra来解决这个问题吗？
任何解决办法都将不胜感激。
浏览 2提问于2015-02-16得票数 4
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
