A-B-C-DG OH PI QJ RK-L-M-N21当我使用djikstra的算法时，主要的问题是我不能得到从源到目标的最短路径算法遍历不在最短路径中的节点，以找到最短路径</e
浏览 18提问于2016-08-07得票数 1
1回答
这个问题基本上是关于在加权图中寻找最短路径。我对这些类型的问题非常陌生，我想我可以使用Dijkstra的算法。然而，有一个小的复杂性-某些值是不同的，取决于当前路径的情况。条件是:当你用权K穿过边时，所有其他类型的权值都是0。这就带来了更多的问题，因为表观最短路径可以用边与K型权值的组合进行打法。下面是这类问题。如果不改变权值，我们就可以很容易地用Dijkstra找到最短<
浏览 5提问于2017-02-16得票数 2
回答已采纳
我正在寻找一种方法来扩展BFS方法，用于在无权有向图中找到单源最短路径，并在O(N+M)时间内解决上述问题。其中N是顶点数，M是边数。
收缩图的顶点，在它们之间有一个边权0。将边权值改为1和2，然后在长度为2的路径中创建虚拟顶点，将这些边转换为权重1的边，但这会给出错误的答案。在更一般的情况下，当边权在线性时间中介于0和最大值之间时，如何在有向图中找到单源最短路径</e
浏览 1提问于2014-02-02得票数 8
回答已采纳
1回答
我想找出加权有向图中由4条边构成的最短圈(最短=边的最小权和)。
我知道我可以使用弗洛伊德-沃尔算法来寻找图中的最短圈，如所描述的那样。但我不知道如何才能找到由四边构成的最短循环。
浏览 2提问于2015-04-11得票数 1
回答已采纳
2回答
Dijkstra的最短路径算法会在具有负权边的有向树上返回正确的结果吗？
在具有负权重的一般图上，该算法将失败，但由于它是一棵有向树，因此感觉该算法会成功。
浏览 5提问于2022-06-01得票数 2
我目前正在研究非负边权图中的最短路径问题。我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这
浏览 4提问于2022-05-11得票数 2
我想找到一条从s到t的路径，它最小化了路径上的总重量。当然，当负循环存在时，它可以进入负无穷大。但是，如果我不允许在路径中循环(而不是在原始图中)，该怎么办？也就是说，一旦路径离开一个节点，它就不能再次进入该节点。提前谢谢。实际上，给出了一个具有非负边权的循环有向图。此外，每个节点也有一个积极的回报。我想找到一个简单的路径，它最小化(路径<
浏览 2提问于2013-10-22得票数 2
回答已采纳
4回答
首先，让我们定义算法：我想知道如何使用Dijkstra算法将最短路径形式s保存到t。如何使用Dijkstra保存从s到t的最短路径？
我知道我的问题是基本的和不专业的，但任何帮助都将不胜感激。谢谢你考虑我的问题。
浏览 6提问于2015-03-11得票数 11
回答已采纳
1回答
给出了边权为整数(正、零或负)的n个顶点加权有向图，确定是否有任意大权的路径可以在时间-中执行。O(n)O(n^1.5)而不是O(nlogn)O(2n)但不是O(n^3)
我不知道用什么算法来寻找最长的路径是一个NP
浏览 1提问于2018-05-29得票数 0
回答已采纳
允许多次沿边缘旅行，尽管这将使解决方案更加昂贵--以3倍的成本沿边旅行将使整个路径的成本增加6倍。这个图有一些“死胡同”的节点，所以有时我们不得不不止一次地遍历一个边。我将用python写这篇文章。因此，如果您知道该算法的任何python实现，这是最好的。
浏览 3提问于2012-09-05得票数 4
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。附注：我很难证明MST包含每个顶点的有向图的最短路径。
浏览 1提问于2012-11-08得票数 0
1回答
我有一个关于如何在具有简单边的无向图中找到最短路径和最长路径的一般问题，其中边没有权重。我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？我知道当我们使用BFS时，我们逐层访问节点，我们可以使用它来寻找最短路径(这可能就是为什么Dijkstra是基于BFS或类似于BF
浏览 42提问于2021-03-26得票数 0
2回答
我正在做一项任务，它让我遍历一个简单的正方形图，目的是积累最少的危险。终点很简单:从左上角到右下角。我只限于水平和垂直移动之间的顶点。地牢里的每个房间(图上的每个顶点)都有一个特定的危险等级。0 7 2 5 4 0 -> 1 -> 1 -> 2 -> 2 -> 1 -> 3 -> 1 -> 01 2 2 1 1 1 1 9 1 0我可以尝试Dijkstra的算法，但我不是计算节点之间的距离，而是
浏览 0提问于2015-05-12得票数 1
回答已采纳
在Bellman算法()的塞奇威克和韦恩实现中，findNegativeCycle使用EdgeWeightedDirectedCycle ()在最短路径树( edgeTo数组中的边缘)中寻找有向循环。问题：如果最短路径树同时包含零权循环和负权循环，那么如何确保EdgeWeightedDirectedCycle不返回零权循环(从而导致断言失败)？
浏览 2提问于2020-11-26得票数 4
我的任务是设计一个算法，在具有V节点的加权无向图中寻找最短路径，并在O(V + E)时间内找到E边。图的权重都是正整数，没有权大于15。我相信我可以使用Dijkstra的算法找到从源节点到目标节点的最短路径，但我认为它不满足运行时约束。我知道在BFS和DFS的运行时，我认为使用这些算法进行某种修改将使我进入O(V + E)，但我不知道该朝哪个方向前进，也不知道如何利用<= 15的边权约束。
任何帮助都是非常感谢的。
浏览 2提问于2019-10-31得票数 1
回答已采纳
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径
浏览 3提问于2013-09-02得票数 2
回答已采纳
我知道普通的BFS搜索可以用来在无权图或边权相同的图中寻找最短路径，而Dijkstra应该用在加权图中，Dijkstra可以看作是BFS的变体。但我想知道，如果每次更新distw时，我都将节点推送到队列中，而不是在普通的BFS搜索中只推送一次，那么这个算法是否适用于寻找最短路径？
浏览 36提问于2020-12-10得票数 0
回答已采纳
云服务器
ICP备案
腾讯会议
云直播
对象存储
腾讯云开发者
