1回答
好的，我最近一直在教自己Prolog，我很难在列表中的两个(定义的)元素之间找到“最短路径”。它可能不是表示网格或寻找最短路径的最有效方法，但我想尝试这样做。目标是“1”找到通往“2”的最短路径。,o,-,-,-,o,x],注意，有两条“最短路径”：和在Prolog中，我试图
浏览 2提问于2013-12-03得票数 1
回答已采纳
3回答
我们得到一个加权图G和它的最短路径距离的矩阵Δ。因此，Δ(i，j)表示从i到j最短路径的权重(i和j是图的两个顶点)。初始给定的增量包含最短路径的值。突然，边E的权重从W减少到W‘。如何更新O(n^2)中的增量(i，j)？(图的顶点的n=number)问题不是再次计算具有最佳O(n^3)复杂度的所有对最短路径。问题是更新增量，这样我们就不需要重新计算所有对的最短路径</em
浏览 2提问于2010-12-17得票数 4
我想修改BFS算法，得到包含字母'c'，'o'，'d'，'e‘的最短路径。这四个人之间可能还有其他信件。您有开始节点'a‘和结束节点'b’。您可以假设这始终是一条按顺序包含这四个字母的路径。
浏览 4提问于2017-10-21得票数 1
回答已采纳
我修改了Dijsktra的算法，该算法寻找两个节点(s和v)之间的最短路径，而不是寻找从节点s到v的最短路径上的最后一条边，标记为X。现在，如果我得到了所有标记为X的节点，我应该使用X节点来回溯我的步骤，以找到s和v之间的最短路径。
我的问题是:这个修改后的算法的大O是什么？
浏览 1提问于2016-02-10得票数 0
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
如果有一个矩阵和两个已知点，那么如何在这两个点之间创建一个随机路径(不需要最短)：
输入后：pt1 = [2,1]; pt2 = [5,5];。如何获得这样的模式，如在参数中记录的路径，如path = [2,1;2,2-;3,2;4,2;4,3;4,4;4,5;5,5]。X X X
浏览 2提问于2014-03-16得票数 4
回答已采纳
1回答
带锁边和无锁定边无向图的最小路径
、、、、
确定给定的边是锁定的还是未锁定的边取O(1)。
对于给定的两个顶点s，t和一个正数k= O(1)，如何在s和t之间找到包含的最短路径？对于两个顶点s，t和一个正数k= O(1)，如何找到包含k锁定边的s和t之间的最短路径？我不知道如何在这个图上运行Dijkstra算法来找到给定顶点之间的最短路径，以及如何将无向图转换为有向图。
浏览 3提问于2013-06-24得票数 2
3回答
我正在实现一个k-最短顶点不相交路径算法，需要一个快速算法来找到最短路径。有负权重，所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到的一篇论文中，作者使用了一种所谓的SPFA算法来寻找负权重图中的最短路径，根据他们的说法，该算法的复杂度为O(e)。听起来很有趣，但我似乎找不到关于算法的信息。另外，有没有解决k-最短顶点不相交路径问题的来源？我什么也找不到。
谢谢!
浏览 3提问于2011-10-10得票数 4
1回答
大地图上的寻路
、、、
我希望用户能够设置一个位置，并让计算机立即找到最佳路径。然而，由于映射是10,000×10,000，所以有100,000,000个节点，通过诸如A*或Dijkstra的传统方法来找到这条路径将需要大量的内存和很长的时间。所以我的问题是:我怎样才能找到最佳路径？
我正在考虑的算法将把世界分成100个部分，每个部分有1,000,000个节点。然后，每个部分将被划分为100个子部分。然后，该算法将找到部分的最佳路径，然后是子部分，然后是子子部分，直到找到最佳节点集。这行得通吗?有没有更好的办法？
浏览 83提问于2016-05-27得票数 21
回答已采纳
1回答
我要设计一个算法，运行在O(k(m + n))内，用于报告从s到t的k边最短路径。k边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，路径的总权重也必须是最小的。由于BFS不能单独使用来寻找最短路径(除非权重相等)，我认为运行时间意味着使用BFS来寻找具有k条边的路径。让我失望的是k，因为我认为它意味着要执行k次BFS。我可能的想法是从源运行
浏览 0提问于2013-03-14得票数 1
1回答
我有一个关于如何在具有简单边的无向图中找到最短路径和最长路径的一般问题，其中边没有权重。我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？我知道当我们使用BFS时，我们逐层访问节点，我们可以使用它来寻找最短路径(这可能就是为什么Dijkstra是基于BFS或类似于BFS的原因)。但我看不出我们如何有效地找到使用BFS的最
浏览 42提问于2021-03-26得票数 0
希望找到从节点a到任何节点的最短加权路径。未给出目标节点。一个人可以多次访问任何一个顶点。下一步的算法是什么？？无法检测到算法本身。如何在记忆中记住所有的道路是这里的主要挑战。参考资料：
浏览 2提问于2015-04-05得票数 0
回答已采纳
3回答
我想知道是否有一种算法可以找到从头节点到尾节点的最短节点序列。图从头节点分支出来，并且是任意复杂的，并且在尾节点处收敛。节点之间的所有连接都是未加权的。
浏览 1提问于2010-12-25得票数 4
回答已采纳
我正在寻找一种方法来扩展BFS方法，用于在无权有向图中找到单源最短路径，并在O(N+M)时间内解决上述问题。其中N是顶点数，M是边数。
收缩图的顶点，在它们之间有一个边权0。将边权值改为1和2，然后在长度为2的路径中创建虚拟顶点，将这些边转换为权重1的边，但这会给出错误的答案。在更一般的情况下，当边权在线性时间中介于0和最大值之间时，如何在有向图中找到单源最短路径。(最大值是最大边重)
浏览 1提问于2014-02-02得票数 8
回答已采纳
2回答
给定一个无向(无长度)图G=(V，E)，具有|V|=n和|E|= m，以及两个顶点v，w，找到输出G中最短v-w-path的算法，运行时间应为O(m+n)
我一直在解决这个问题，但是很难让运行时间是O(使用BFS确定最短v-w-path的长度。然后使用DFS求出使得两个节点相连且路径长度等于BFS的输出的v-w最短路径的数目。但该方案的运行时间为O(m+n)+O(m+n)。存储访问节点集合中添加节点时的最短<
浏览 0提问于2014-09-13得票数 0
回答已采纳
1回答
您可以从QR代码顶部的任何位置开始(在第一行中的任何位置)，并且必须找到一条路径来到达底线中的任何位置(最后一行中的任何位置)。你必须最小化路径中的黑箱数，如果你有几条相同数目的黑箱，你必须找到最短的一条。在这些条件下寻找最短路径的算法。一个小值(<<1)在这里寻找最短路径，当我们有相同数目的黑箱数的几条路径。
用这个表示
浏览 3提问于2015-01-19得票数 2
回答已采纳
1回答
书中说，重建最短路径树需要O(n+m)时间。但是，考虑到这些代码，我无法理解为什么它是O(n+m)而不是O(n*m) (因为我们有两个嵌套的for循环，一个嵌套在顶点上，另一个嵌套在传入边上)。书上说：
在这一部分中，我们证明了基于源s的最短路径树可以在O(n + m)时间内重建，给出了Dijkstra算法以s为源产生的dv值集。正如我们在表示DFS和BFS树时所做的那样，我们将每个顶点v =/= s映射到父u(可能的话，
浏览 2提问于2022-07-03得票数 0
回答已采纳
给定一个只有正边权的有向连通图，是否有比使用fibonacci堆的Dijkstra更快的算法来寻找两个顶点之间的最短路径？Wikipedia说，Dijkstra在O中(用fibonacci堆)(使用fibonacci堆)。我不是在寻找优化，例如，一半的执行时间，而是不同时间复杂度的算法(比如从O(n * log n)到O(n))。
确定所有边缘权重的GCD。使用BFS找到两个给定顶点之间的最短
浏览 4提问于2009-11-09得票数 9
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
