在Dijkstra算法中选择最近节点的意义是什么？
在Dijkstra算法中选择最近节点的意义是为了确保计算出的最短路径是基于当前节点到起始节点的最短路径。Dijkstra算法是一种用于计算最短路径的经典算法，它逐步确定从起始节点到其他节点的最短路径，并将其保存在一个距离表中。
选择最近节点的意义主要体现在以下几个方面：
- 最小化计算量：选择最近节点能够减少计算量，因为它确保了每次选择的节点都是离起始节点最近的节点，从而可以快速找到最短路径。
- 保证路径的最短性：选择最近节点可以确保每次计算的路径都是基于当前节点到起始节点的最短路径。通过逐步选择最近节点，并更新距离表中的距离值，最终可以找到从起始节点到目标节点的最短路径。
- 提高算法效率：选择最近节点还可以提高算法的执行效率，因为它能够优先考虑离起始节点较近的节点，减少了搜索的范围，从而缩小了问题的规模。
总结起来，选择最近节点在Dijkstra算法中的意义主要是为了确保计算出的最短路径是基于当前节点到起始节点的最短路径，并且能够最小化计算量、保证路径的最短性，提高算法的效率。
相关·内容
1回答
旅行推销员启发式
、、、
我现在的想法是:从0点开始，把它和最近的点连接起来。对于所有剩余节点，将其插入到所有可能的位置，并保留成本最低的配置。
所以我从0点开始。最接近点0的节点是点1。
所以我现在有0 -> 1 ->0
对于第2点(以及所有剩余的节点)，我将检查新节点可能位于何处的所有可能性：
2 -> 0 -> 1 -> 2
0 -> 2 -> 1 -> 0
0 -> 1-> 2 -> 0
从这里我发现
0 -> 1 -> 2->0的欧几里德距离最小，所以这是我要保持的配置。
我将继续为我的其余节点使用这个逻辑。
是否有一种在c+
浏览 2提问于2016-12-02得票数 1
1回答
我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：
，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。v^2来自shift操作，因为在每个iteration.This BFS解决方案上都可以通过利用类似于Java中的ArrayDeque来改进这一点，这将给我们O(1)操作，每次我们跳出队列的前端，并且应该将我们的时间复杂度降低到O(v+e
浏览 2提问于2021-01-18得票数 0
1回答
我有一个学校的问题，我不确定用什么来编码。假设你有一个无向和无权重的图G，它是一个城市道路网络。节点n是交叉口，m条边是道路。在n个节点中，有h个医院。这个问题想让我们找出每个节点n，从每个节点到最近的医院的距离。是否可以使用BFS，或者djikstra会是更好的选择？
此外，我们还需要提出一种新的算法，找到距离每个节点最近的K个医院，其中K是用户输入。在这种情况下，bfs是否仍然可行，或者djikstra是唯一的解决方案？谢谢。
浏览 0提问于2020-10-20得票数 1
我正在学习Dijkstra的算法，并且有一个基本的查询。我有一个如下所示的图..(非负节点)：
A-2-B-16-D-3-F
**
**
3 4
**
C-2-E
从上面的图表显示不清楚，但AC的距离为3，EF的距离为4。
我对寻找A和F之间的最短路径很感兴趣。
考虑目的节点F，当我们考虑它最近的节点时，我们得到D (DF的权重为3，EF为4)。然而，当我们沿着这条路径走时，我们得到了最短路径: A，B，D，F(总距离: 19)。
快速观察告诉我们，最短路径实际上是A，C，E，F(距离: 9)。然而，由于在第一步中，E比D更远，所以我们遵循D。
我是不是漏掉了什么？Dijkstra的算法显然没
浏览 0提问于2014-03-25得票数 3
我正在开发一个个人项目。在这个视频游戏中有一个基于网格的移动、创建和寻路系统。在此之前，我曾使用A*寻路来使某些字符移动到某个已知位置。
但现在我遇到了一个大问题。在我的游戏中有一个角色必须去一个特定的对象，但是这个角色不知道这个物体的精确坐标。最简单的方法是真正知道这些物体的坐标，计算出哪个是最近的，并使用A*路径查找来达到这个点，但是这种方法看起来确实是被操纵的，而且对我所做的游戏的类型来说还不够动态。
因此，我想知道是否有一些路径查找算法可以在某个点(正在使用该算法的字符的位置)附近搜索，比如以径向方式进行搜索，并一直搜索直到它找到正在寻找并返回到该特定对象的路径的对象类型。
浏览 7提问于2016-06-01得票数 0
回答已采纳
我很难理解实现Dijkstra的逻辑流程是什么，更确切地说，我遇到的问题是如何得到优先级队列，在图上执行算法时是否构建它(优先级队列)？还是我看错了？那就是这样吗？我们是在此停止，还是通过将获取的信息以其他形式放置在优先级队列中来进一步处理该输出，还是在这里停止？
我还理解了为选择的节点生成相应的最短路径的过程，首先递归地按照我们所取的边形成最短路径，但是它实际上是如何实现的呢？
总的来说，我在学习过程中遇到了很多问题--实际上我能够想出和/或理解适当的算法实现，我很好地理解了算法(在某些情况下，我能够想到一个相近的替代)，但是我只是想不出聪明的实现方法，有什么建议吗？
浏览 2提问于2020-04-23得票数 0
回答已采纳
我正在开发一个系统，使用Dijkstra的算法来使用Java在平方网格中显示最短路径。当路径靠近对角线、垂直或水平单元时，路径成本增加1。但是路径的优先级应该是通过对角线单元。只有当附近没有可能的对角线单元格时，路径才能通过垂直或水平单元格。这样做最方便的方法是什么？
浏览 12提问于2017-04-29得票数 5
回答已采纳
从我到目前为止所读到的。在找到到达目标的最短路径方面，似乎更快，因为Dijkstra的算法在遍历图形时必须放松所有节点。是什么让Dijkstra的算法比Best First Search更好？
浏览 1提问于2012-04-30得票数 13
回答已采纳
我正在Android Studio上做一个关于我所在城市的公交路线的应用程序，这是我想要包括的一个功能。但我一直在寻找如何做到这一点，我没有找到任何接近的东西。 我在.JSON文件(经度和经度)中有公交路线，这些路线绘制在地图上。当用户选择目的地时，应用程序会告诉他哪条公交路线是最近的。您是否建议使用SQL来存储路由和进行查询？欢迎任何相关的评论。谢谢。
浏览 18提问于2019-01-20得票数 0
我在研究DFS和Dijkstra。在我的简单测试用例中，大多数测试都表明DFS更快。在我的测试用例中，传递每个节点的成本是一样的。但是大多数人更喜欢Dijkstra而不是DFS，因为Dijkstra是如此精确。
那么，DFS和Dijkstra有什么区别？另外，每种算法的优缺点是什么？
浏览 2提问于2017-12-07得票数 6
1回答
我有6个城市在我的记录里。孟买，blore，Hbad，德里，chennai，pune。并记录每个城市的特色菜。
当用户出现在我的页面上时，我想显示基于位置相关性的记录。我想用最短的距离。
从用户的IP，我可以得到他的位置(城市或朗拉蒂)。我想要计算用户与上述每一个城市的距离。这是最近的，我应该选择它来显示记录。
有什么更好的方法吗？我正在使用php。
请在执行层面上谈谈..。
浏览 1提问于2014-01-25得票数 1
回答已采纳
目前，我已经实现了Dijkstra的最短路径算法。给定一个迷宫，最短路径算法提供了以最少的步数从入口到出口退出迷宫的最快方法。然而，我想找到一种方法，给定特定的n步，迷宫中可能的最大路径是什么？(您可以到达死胡同并返回，这将被算作额外的步骤)
浏览 31提问于2019-04-27得票数 0
2回答
给定一个加权无向图，需要找到两个节点之间的最短路径，这实际上是一个经典的最短路径问题。但是还有一个约束:每个节点都包含一个“约简”值，可以用来降低一个遍历的下列边的成本(不仅是相邻的，而且约简也不是累积的)。因此，您可以使用您之前所经历过的一个节点中的“约简”来降低边缘的成本(每个边的最终成本不能小于0)。
请注意，一旦我们通过一个节点的缩减，我们可以再次使用它的所有以下边缘(不只是相邻的，它是可以无限的时间)。减少不会累积。
让我们考虑一下这张图：
在此图中，从节点1到节点5的最短路径是：
1 -> 4，费用13 (15-2)
4 -> 3，费用为0 (12-1
浏览 0提问于2018-02-17得票数 2
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
8回答
在图论的背景下，relaxation of an edge是什么意思？我是在研究Dijkstra的单源最短路径算法时遇到这个问题的。
浏览 8提问于2012-10-08得票数 58
回答已采纳
1回答
我有一个二维的数字数组，我的任务是找到从起始索引0,0到结束索引的最小上升或下降量。
制约因素是我们不应该以对角线旅行。
示例：
1 2 3
1 2 0
6 3 2
解决方案：
Path --> 1 -> 1 -> 2 -> 3 -> 2.
1-1 = 0
2-1 = 1
3-2 = 1
3-2 = 1
Result = 0 + 1 + 1 + 1 = 3
解决这个问题的方法是什么？
更新：
我使用代码传递输入的2D数组，并将V=3设置为数组有3行，不确定是否正确设置了V值。
我在代码中设置的2D数组是：
int graph[][] = new int[][]
浏览 3提问于2019-10-02得票数 0
最近，我将Dijkstra算法的第三个版本的单源最短路径附加到我的项目中。
我意识到有许多不同的实现，它们的性能差别很大，而且在大图中结果的质量也不同。对于我的数据集(> 100.000个顶点)，运行时从20分钟到几秒不等。最短的路径也有1-2%的变化。
你知道哪一个是最好的实现？
编辑： My是一个液压网络，每个节点有1到5个顶点。它可以与街道地图相媲美。我对一个已经加速的算法进行了一些修改(对所有剩余的节点使用排序列表)，现在只需一小部分时间就可以找到相同的结果。我已经找了很久了。我想知道这样的实施是否已经存在。
我无法解释结果的细微差别。我知道Dijkstra不是启发式的，但是所有
浏览 7提问于2009-06-02得票数 12
回答已采纳
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
回答已采纳
1回答
我目前正在为我的一次考试做修改，我已经回答了这个问题，“逐步显示，使用Dijkstra的算法在图中找到从顶点A到彼此顶点的最短路径。在每一步，已知的和边界的集合都应该清楚地显示出来。”我知道如何找到最短的路径，但我确信什么是边框集？谢谢!
浏览 1提问于2017-05-04得票数 2
回答已采纳
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
1回答
迷宫解算的最佳算法？
、、、、
最近我做了一个项目，用不同的路径搜索算法来解决一个给定的迷宫。为此，我导入了一个黑白迷宫图像，并使每个节点成为一个节点。我尝试使用DFS、BFS、Dijkstra和A*来解决这个问题，但注意到DFS给了我最短的运行时间。那么，我的问题是，在一个完美的迷宫(只有一个解决方案的迷宫)上使用更先进的算法(比如Dijkstra或A* )是否有意义？或者，这些算法只在有多种解的迷宫中才有意义？
我在网上研究了这个问题，发现很多人喜欢用A*来解决这类问题，但我不明白这怎么会更好，至少对于一个完美的迷宫来说是这样。
浏览 3提问于2020-04-14得票数 3
回答已采纳
在最近的一次采访中，我被要求实现单源最短路径算法(对于无向和正加权图)，即给出一个额外的边，其权重'w‘。我们必须找到一条比SSSP algo计算的更短的路径，方法是将两个尚未连接的节点之间的额外边连接起来，并加上权重'w‘。
但考虑到额外的优势。它可以连接在A和D之间，而D和A之间还没有连接，从而使通过SSSP algo产生的最短路径最小化。
我试着考虑解决办法。但到目前为止什么都没有发生。我已经实现了Dijkstra算法来找到最短路径。但这个小小的改动让我很困惑。你能帮点忙吗。
浏览 4提问于2016-10-17得票数 3
回答已采纳
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
回答已采纳
1回答
一种基于Dijkstra的算法
、、、、
给出了一个边权为w:E到R+的有向图G= (V，E)。
这张图代表布鲁克林的道路，每条边缘的重量表示道路的长度(以英里为单位)。奖品放在节点t( V)上。给定的是V中的一组节点A (A是V的子集)，函数s:A到R+。
在A中的每一个v中都有一个球员。在比赛开始的时候，所有的玩家都同时离开，朝着奖品前进。
每个玩家都以最短的路径从其起源节点到t，离开节点v的玩家以恒定的速度进行s(v)，也就是说，对于e中的每一个E，它用这个玩家w(e)/s(v)时间单位横过e路。
建议一种有效的算法来返回赢家。
我的尝试：
算法：
在A中的某个节点v上运行Dijkstra，并为A中的每个v启动一个大小为的数组
浏览 1提问于2021-11-11得票数 0
回答已采纳
4回答
首先，我知道Dijkstra不适用于负重，我们可以用Bellman代替它。但是在一个问题中，给出了所有边都有从0到1的权重(0和1不包括在内)。路径的成本实际上是产品。
所以我想的是把日志拿走。现在所有的边缘都是负值。现在我知道Dijkstra不会对负重起作用，但是在这种情况下，所有的边都是负的，所以我们不能做一些事情，这样Dijkstra才能工作。
我想把所有的权重乘以-1，然后最短的路径变成最长的路径。
在这种情况下，我可以避免使用Bellman算法吗？
确切的问题是：“假设在某些应用中，一条路径的代价等于路径中所有边的权重的乘积。在这种情况下，如何使用Dijkstra算法?所有边的权重从
浏览 3提问于2015-04-18得票数 7
回答已采纳
1回答
根据问题的具体情况，在单源最短路径问题中通常提到的两种算法是Dijkstra算法和Bellman算法。Dijkstra的算法工作在正边权值，而Bellman算法是一个推广，也允许负边权。
正如Sedgewick的“算法”(第4版)所实现的，Dijkstra的算法是基于优先级队列的，而Bellman-Ford算法是基于一个普通的FIFO队列的。然而，在我看来，这两种队列类型的选择都不是实现算法所必需的。我们也可以用FIFO队列来实现Dijkstra的算法，用优先级队列实现Bellman算法。
为什么Dijkstra的算法通常是用优先级队列来实现的，Bellman则是用FIFO队列实现的呢？是出于
浏览 7提问于2015-04-18得票数 0
1回答
我最近不得不看看Dijkstra算法，它证明了这一点。
算法的证明在我能找到的所有来源中终止，所有顶点的数量和访问的所有顶点的数量相等(例如R=V或S=V)。此外，当Q(作为图的所有顶点初始化)为空时，该算法的while循环终止，因此必须访问所有顶点。
我不明白为什么一定要这样。有没有这样的图，算法不必访问所有的顶点，例如:起始顶点直接连接到权重为1的“查找”顶点，并连接到权重为10的其他顶点。
我希望你能理解我在这里遇到的问题。
编辑:这是我在科尔曼使用的伪代码：
浏览 2提问于2018-06-08得票数 2
如果给定图中的所有边都有相同的权重，Dijkstra的算法还能找到两个顶点之间的最短路径吗？谢谢!
浏览 6提问于2014-01-24得票数 3
回答已采纳
我有一个图，我想对它使用apoc dijkstra算法，到目前为止一切都正常。但我希望从可能的路径中排除某些节点或节点属性，这样dijkstra算法就不会返回包含这些排除的节点或属性的路径。
例如，是否可以在调用apoc.dijkstra算法之前过滤所有现有节点？
我知道在算法之后过滤找到的路径是可能的，但也有可能在图中有一条可能的路径没有找到，因为过滤节点发生在之后。
浏览 11提问于2020-05-27得票数 0
回答已采纳
2回答
复杂寻路算法
、、
我正在为一个3D游戏编写一个系统，它允许摄像机在节点网络之间移动。
在我的项目中，我编写了一个表示节点的类。与二进制节点类不同，每个节点只能有一个父节点，但允许有任意数量的子节点。利用我真正令人惊叹的绘画技巧，我开发了一个图像，它代表了这些节点的网络：
在本例中，“根节点”是红色的，黄色路径是最短的，蓝色路径是最长的。
这里需要注意的是，子节点的实际数并不重要，而是它们之间路径的加长。因此，在计算最短路径时不需要启发式，因为最短路径的合并长度最小。
那么，如何编写递归函数来遍历这棵树，并返回最短路径呢？
更新
虽然我的绘画技巧很棒，但我觉得它并没有充分说明我的问题，也许需要更详细的
浏览 6提问于2016-04-26得票数 3
回答已采纳
1回答
我正在寻找双向搜索的实现(也就是。对于Java中的Dijkstra (或任何其他源到目的地的最短路径算法)，可以使用“中间相遇”算法。
由于双向搜索处理比看起来更复杂()，我想在重新发明轮子之前考虑一下现有的实现！
附言:我说的是，不要与双向图混淆)
下面是一个棘手的图表示例：
浏览 3提问于2012-05-28得票数 9
回答已采纳
1回答
我有一个有一些边的图。每个边都有一个权重/成本，还有一个标签/类型，可以是red和green。
我知道，如果我运行Dijkstra算法，它将从所有边的权重中找到最短/最便宜的路径。然而，我的问题是，取决于它选择哪种类型的边缘，应该增加额外的成本。原则上，只应在每次使用新类型时添加额外费用。
例如，如果我从Dijkstra找到的路径是：
node1 ---> node2 ---> node3 ---> node4 -----> node5 -----> node6
|---- edge1 --|-- edge2 ---|--- edge3 -
浏览 1提问于2021-06-22得票数 1
回答已采纳
1回答
我试图在无向加权图中找到两个顶点之间的最短路径。我们还知道，权值小于log(log，x，v，x，x)，其中，x是顶点的数量。使用Bellman或Dijkstra算法很容易解决，但是有什么算法可以更快地解决吗？
到目前为止，我一直在考虑使用BFS，并将权重大于1的边分割成一对权重为1的边，但是如果向量V是大数的话，这并不是什么好主意。不，这不是我的作业，我只是想知道。
浏览 0提问于2018-06-06得票数 0
回答已采纳
Dijkstra的O有一个运行时间，而BFS的运行时间为O。
那么为什么dijkstra更理想呢？看来它的运行时间更长了。
编辑:请看有标记的答案。结果显示，我在加权图(基本上是蛮力)上使用BFS对最短路径的运行时间分析是不正确的。在加权图上使用蛮力BFS具有O(V!)的上界。Dijstra是更理想的。
浏览 0提问于2019-02-03得票数 2
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
1回答
对于从柠檬图库(柠檬的Dijkstra的)运行Dijkstra算法所需的一些参数，我有一个问题。要运行该算法，可以编写类似于dijkstra(g, length).distMap(dist).run(s,t);的东西，其中g是图形，s是起始节点，t是目标节点。我的问题是length和dist是什么，以及它们是如何使用的。谢谢!
浏览 3提问于2012-08-13得票数 1
1回答
给出了一个有向加权图，它有m个边和n个顶点。每条边的重量都是非负的。顶点要么在集S1中，要么在集S2中(S1和S2是不相交的)。您需要在任意对 (v1，v2)之间找到最短路径(v1在S1中，v2在S2中)。
解决方案的运行时间应该是O(mlogn)。
‘非否定’和'mlogn‘让我想起了 Dijkstra ，但我不知道如何使用Dijkstra来解决这个问题。
提前谢谢。
浏览 3提问于2022-04-27得票数 0
回答已采纳
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
让我们使用给定的值( sayIi，Destiny，Distance)：
A ~ B = 5
B ~ C = 10
A ~ C = 20
我想找到从A到C的最短路径(在本例中是A->B，B->C)。
存储/搜索这些值的最佳数据结构是什么？
浏览 0提问于2017-08-19得票数 0
4回答
我正在尝试用C++创建一个简单的基于网格的游戏。寻路是其中必要的一部分。我一直在找，但并不完全是我要找的。
规则很简单。有一张地图。大小一般不超过100 x 100平铺。1是地砖，0是墙。不允许对角线移动，因此每个网格只有4个方向。然而，大多数情况下都有不止一个目标。我想找一条最近的路。记住，我们不能只计算距离公式，哪一个是最近的。距离短的目标可以走更远的路，因为有墙。我认为使用一种已知的算法，并为每个目标重复，这不是一个好主意，因为它会变慢。
你的意见呢？我该怎么办？
浏览 0提问于2015-03-04得票数 1
4回答
让我们考虑一个简单的网格，其中任何点最多与其他4个点(东北-东-西-南邻域)相连。
我必须编写程序，计算从选定的初始点到的最小路径，任何目标点的都是连通的(在任意两个目标之间存在由目标点组成的路径)。当然，网格上也会有障碍。
我的解决方案很简单:我使用的是带有可变启发式函数h(x) -曼哈顿距离的A*算法，从x到最近的目标点。为了找到最近的目标点，我必须进行线性搜索(在O(n)中，其中有n个目标点)。下面是我的问题:是否有更有效的解(启发式函数)来动态地找到最近的目标点(时间< O(n))？
或者A*不是解决这个问题的好方法？
浏览 9提问于2011-12-26得票数 11
回答已采纳
1回答
有N个网络节点，标记为1到N。 给定时间，作为有向边的行进时间列表timesi = (u，v，w)，其中u是源节点，v是目标节点，w是信号从源节点到目标节点所需的时间。 现在，我们从某个节点K发送信号，所有节点需要多长时间才能收到信号？如果不可能，则返回-1。 这是我的代码..然而，它给出了错误的答案 class Solution {
public:
int networkDelayTime(vector <vector<int>> ×, int N, int K) {
vector<int> time(N +
浏览 24提问于2020-07-15得票数 0
1回答
我试图实现dijkstra的最短路径算法使用地图缩减。
我有两个问题：
这种算法是否回溯，以重新评估距离，以防距离被证明是较少的非选定的路径。例如，-> 1->2->5和2->3->2认为这些值是权重，并且可能的2条通往目标路径1的路径被选择为1<2，但是对于路径2，即2->3->2，总权重之和较小，因此想知道dijkstra的算法是否考虑了回溯。
请给我一个简单的想法，地图和缩减功能将如何在这种情况下。我正在考虑在映射函数中发射作为和在约简函数和在减少函数，我迭代相关的权重，以找到最小加权邻域..but之后，它的工作方式。请给我一个很好
浏览 3提问于2013-12-08得票数 0
我的研究是寻找一个最短的路径之间的起源和目的地预定义。(原点和目的地)都是使用GIS扩展来定位的，因为它们是由一个形状文件获得的。我使用命令ask patches gis:intersecting shapefile在原点创建一个人，在目的地创建一个学校。
我有10个起源，每一个我都有一个指定的目的地。我注意到，当我使用Dijsktra算法寻找最短路径时，对于某个原点，目的地不是各自的点，而是最近的目的地。所以，我的疑问是:Dijsktra是解决我问题的最佳算法，还是我需要使用A*算法？
如果Dijsktra的算法是最好的，我如何在代码中通知对的起源和目的地？
如果A*算法是最好的，我如何构造
浏览 2提问于2014-02-12得票数 0
回答已采纳
我正在寻找关于从哪里开始寻找解决这个问题的方法的指点。
在谷歌搜索了一段时间之后，我发现的唯一问题就是一个。区别在于，我不是在寻找一棵树，它跨越了图中的所有顶点，而是谁跨越了给定的3个顶点。
我不是在寻找一个完整的程序，而是一个指向总体方向的答案。
我的另一个想法是使用运行3次搜索。这个想法是通过组合不同的最短路径来找到最好的路径。我不知道如何做到这一点。
下面是我所讨论的图形类型的一个图形示例：
因此，我们的任务是找到一种方法，在这类图中找到连接任意三个顶点的最小和权。
编辑:
我用Dijkstra的算法进行了3次搜索，解决了这个问题。然后，通过添加所有的单边，找到了连接三个顶点的
浏览 11提问于2013-12-27得票数 2
我感兴趣的是寻找从网络中的所有点到特定点的最短路径。到目前为止，我一直在通过循环遍历所有点来计算最短路径来估计这一点。 随着网络规模的增加，这种方法的计算代价很高。有没有有效的替代方案？在NetworkX中有什么我忽略的地方吗？ # Pseudocode
For a_node in list_of_nodes:
shortest_path_to_poi = nx.shortest_path(G, source=a_node, target=poi, method='dijkstra') 感谢您的时间和调理。
浏览 51提问于2020-07-04得票数 0
回答已采纳
我想知道二进制、二项式和Fibonacci堆之间的基本区别，以及它们最适合使用的场景。我主要关注的是他们在Dijkstra算法中的应用，根据所使用的堆的类型，它的时间复杂度将如何变化？
浏览 1提问于2015-11-20得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
