当图G分别具有顶点和边，顶点u和t时，编写一个O(|E|+|V|)算法计算从u到t的最短路径数，即如果有5条长度4的路径，长度4是从u到t的最短路径，则算法输出5条。我知道算法必须以某种方式合并DFS或BFS，因为每个算法都有一个O(|E|+|V|)运行时，但我有点卡住了。我尝试实现这样的东西:它会反复执行DFS，算法终止于t，但在决定将哪些节点设置为已访问的节点以及在每次迭代后重置哪些</
浏览 0提问于2019-04-17得票数 0
回答已采纳
11回答
图中节点之间的最短路径可以通过几种算法(Dikstra，A-star等)找到。请仅提供一个应用程序/答案！解释应用程序，以及如何将其转换为最短路径问题。
浏览 0提问于2010-12-11得票数 13
1回答
我最近问了一个关于Dijkstra算法()的问题。但几乎每个人都认为“Dijkstra算法”是指他的最短路径算法。
Dijkstra还开发了哪些算法？
浏览 0提问于2010-06-02得票数 16
回答已采纳
1回答
在允许对角线移动的网格中测量两个节点之间的距离的正确算法是什么？
我曾想过使用欧几里德距离，但被告知这是错误的。
浏览 1提问于2015-09-20得票数 1
3回答
地图上多个点之间的距离
、、、、
我有一个20,000点的gps位置。
我应该得到最短的路径，并把它分解成路线，还是得到路线，然后找出每条路线的短路路径。
浏览 3提问于2013-10-02得票数 0
1回答
此输入将描述我需要在此特定迭代中使用这些点中的哪些点。(本质上，用户将输入需要哪些点)。例如，输入向量可以是V=1 0 1 0 0；这意味着我只需要查看点A和C。然后，基于此输入，我需要使用TSP类型的算法来求解这些坐标之间的最短路径。在这个例子中，我会将矩阵Coordinate=0 0；2 1；输入到我的算法中，以找到最短路径。
浏览 1提问于2013-05-26得票数 1
因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。
问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B；C，K的最短路感兴趣，我们可能只需要一次就能找到两条路吗？
浏览 2提问于2018-03-12得票数 1
我已经创建了这个算法来获得地图上两个选定点之间的最短的点。for (int k = 0; k < count; ++k) for (int+ dist[k, j]; }
浏览 3提问于2014-05-17得票数 0
1回答
我目前正在尝试理解Yen的k条最短路径算法。我以原始论文和维基百科文章为基础，但仍然不明白为什么k> 2是正确的。事实上，我甚至不明白为什么它适用于以下例子：例如，让我们考虑从A到D的3条最短路径，即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该算法的了解，正确地计算了2条最短路径。然而，第三条最短
浏览 0提问于2016-05-01得票数 2
回答已采纳
1回答
首先，让我们定义算法：
Dijkstra算法在具有非负边权的有向图中寻找单源最短路径.如果我有一个源S和目标T，我可以用Dijkstra算法在这两个顶点之间找到最短路径，但是我想要找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过形式K。第一部分是Dijkstra算法，第二部分是BFS算法，因为我们可以用BFS算法在无加权图中找到最
浏览 2提问于2015-02-16得票数 4
回答已采纳
3回答
我需要帮助找到有向无权图中两个节点之间所有最短路径的数目。对我能用的算法/伪码有什么想法吗？
谢谢！！
浏览 7提问于2016-01-14得票数 1
回答已采纳
2回答
今天我遇到了这个词“单对最短路径问题”。我想知道对加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想，如果你想找到A和Z之间的最短路径，你绝对必须知道从A到B，C，D，……的最短路径。Y.如果你不知道后者，你就无法确定你的道路实际上是最短的。因此，对于我来说，任何最短路径算法都必须计算出图中从A到其他顶点的最短路径，才能
浏览 4提问于2017-03-30得票数 10
回答已采纳
3回答
我正在实现一个k-最短顶点不相交路径算法，需要一个快速算法来找到最短路径。有负权重，所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到的一篇论文中，作者使用了一种所谓的SPFA算法来寻找负权重图中的最短路径，根据他们的说法，该算法的复杂度为O(e)。听起来很有趣，但我似乎找不到关于算法的信息。有没有人有好的信息或者这个算法<
浏览 3提问于2011-10-10得票数 4
1回答
我需要一个algorithm(k, s)
算法找出从一个节点到另一个节点的最短路径，而不是
浏览 2提问于2014-10-20得票数 1
1回答
我目前正在为我的游戏寻找路径，需要帮助找到一种有效的算法来计算加权无向图中的所有对最短路径(图中的每个顶点代表我地图上的一个路径点，而每个边表示路径对之间的距离)。由于Floyd算法的简单性和相对存储效率，我考虑过使用Floyd算法，但是Floyd是为有向图设计的，而我的图是无向图。这意味着Floyd算法比所需的代价更高，因为我知道从顶点A到顶点B的最短路径总是与从B到A的
浏览 0提问于2011-09-14得票数 2
回答已采纳
为了完成规划，我必须知道我将在我的项目中使用哪些算法或技术。这个想法非常简单。我只想确定我现在所在的位置和几家超市之间的最短路径/距离。
有没有什么算法或者Android API可以应用？
浏览 1提问于2011-10-18得票数 5
回答已采纳
我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。
我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都是非循环的吗？
浏览 13提问于2017-06-20得票数 0
3回答
如何为每个顶点找到不会导致循环的所有可用路径？使用什么算法？请简明扼要，如果可能，请提供链接，如果下面的精彩图表中有不清楚的地方，请提出问题:)
我不是在寻找最短的路径或类似的东西。相反，我只想知道我仍然可以在我的图形上绘制哪些路径，而不会导致循环。例如，L4可以转到L1, L2, L5，L2可以转到L5...and，等等。我想我想要一个有向无环图，并且需要帮助找出使用哪种算法以及如何使用？
浏览 1提问于2010-10-15得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
