dijkstra

0热度

1回答

我有一个具有约5000个节点的双向加权图表我有一个“重要”节点（100左右）列表。给定一个起始节点和一个结束节点，如何找到这两个节点之间的最短距离，这两个节点至少通过一个“重要”节点。请注意，没有负面的边缘。我实现了dijkstra的算法来找到给定两个节点的最短距离。我知道如何解决这个问题的唯一方法是查看重要节点列表，找到所有重要节点从开始 - >重要节点＃1 - >结束的距离，然后取最小值。有

0热度

1回答

任何人都可以描述Dijkstra算法的这部分代码

我不明白Dijkstra算法的这个给定的部分。我想逐行理解这部分代码。代码： bool operator < (const DATA &p) const { return p.dist > dist; } 我的C/C++代码的基本知识。

2热度

2回答

Python的广度优先于谷歌FOO条（准备兔子逃脱）

我工作了下面的问题，我认为我有它主要是解决最短路径，但是一些测试用例执行失败：你有空间站的部分地图，每个从监狱出口开始，并在逃生舱的门口结束。该地图以0和1的矩阵表示为，其中0是可通过的空间并且1是不通过的墙壁。监狱外的门位于左上方（0,0），进入逃生舱的门位于右下角（w-1，h-1）。编写一个函数答案（地图），它可以生成从监狱门到逃生吊舱的最短路径长度，您可以在此处移除一堵墙作为重建计

0热度

3回答

如果2个图节点之间的间接路径比直接路径短，Dijkstras算法能检测到它吗？

Dijkstras算法假设基于起始节点和中间节点之间的边权重的最近邻居。重复此操作直到到达目的地节点。如果启动节点和中间节点之间的最短路径是通过其他几个中间节点的间接路由，该怎么办？

0热度

1回答

修改Dijkstra以保存具有相同值的路径 - StackOverflow错误

我试图修改Dijkstra的算法以显示所有具有最小值的路径。所以我决定使用以前的顶点列表。我添加了一个if子句，用于检查路径是否为具有最小值的前一个值，并将前一个顶点添加为当前父元素的父元素。问题是我得到一个StackOverflow错误，我不知道是什么导致它。这是我的代码：下面的代码的目的是为图中的所有顶点计算Dijkstra，计算顶点出现在最小路径中的次数，并按降序显示它们全部。 pub

0热度

1回答

有人可以检测到在这段代码中使用python实现dijkstra算法的错误吗？

我想实现dijkstra的算法（在无向图上）找到最短路径，我的代码是这样的。注意：我没有使用堆/优先级队列或任何东西，但邻接列表，字典存储权重和布尔表，以避免在循环/递归循环永远。此外，该算法适用于大多数的测试案例，但未能为这个特殊的位置：https://ideone.com/iBAT0q 重要：图形可以从V1到V2（反之亦然），你必须使用最小重量有多个边缘。 import sys sys.

1热度

1回答

制作Dijkstra算法账户回程时间

这样的问题去如下：未加权树提供给我，让我可以在任一节点，即时通讯预计参观的是香港专业教育学院在阵列中提供了只有特定的节点启动。我的目标是找出需要花费的时间来到每个节点。每条边都需要一分钟才能通过。我已经尝试实现Dijkstra算法，以便开始在我想参观，并试图从那里形成的最短路径的节点。但我的问题是，虽然提供了一个解决方案，但它可能不是最有效的解决方案，因为我不知道如何强制Dijkstra算法来

1热度

1回答

我正在尝试实现类Dijkstra的算法

我应该得到0-3-6-5作为成本的输出。 -1-0-3-1用于前一个数组的输出。和1-1-1-1为访问数组。我得到了0-3-7-5为我的输出成本和-1-0-1-1为以前。如果可以的话请帮忙。我试图看看7是什么时候它应该是一个六，而我没有搞清楚。这是我第一次用C语言进行编码，因此看起来有点草率。 #include <stdlib.h> #include <stdio.h> #include

0热度

1回答

以最少的跳数穿越阵列，面向科技公司面试的在线编码挑战

我做了一个面试问题/编码挑战，我需要通过数组“arr”提出最短的“跳数”，其中每个我可以跳转1-> arr [i]。一个难题就是我不能登陆任何以0为值的索引。当我开始研究这个问题时，我开始将数组作为一个有向图，其中每个索引都是节点i，并且他们的子节点由所有可到达节点i + 1-> i + arr [i]表示。当你想象这是一个图，我认为使用Dijkstra's是一个好方法，因为我不需要遍历数组

0热度

1回答

使用Dijkstra's将2的幂返回相同的最短路径吗？

我有一个图G =（V，E），其中有两个权重函数w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有边缘权重都是独一无二的。在两个权重函数下，Kruskal的算法将返回相同的最小生成树。我知道kruskal是贪婪的，会选择最短/最低成本的路径。既然它们是肯定的，只要没有成本为1.5或者更低的路径，我们最终会选择相同的MST。在两个权重函数下，Dijkstra的算法将返回相同的