2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。附注：我很难证明MST包含每个顶点的有向图的</
浏览 1提问于2012-11-08得票数 0
1回答
G是一个只具有正权的连通无向图。S是最短路径树(不一定是G的防止小组委员会)。因此，我要设计一个算法来检查图S是否是图G的最短路径树。我不知道这个算法是否有效，但我认为它是
浏览 3提问于2014-02-24得票数 1
回答已采纳
1回答
竞争下的预处理最短路径
、、、、
证明了如果P是u与v之间的最短路，那么每个子路也是最短路。给定连通图，我希望预处理矩阵中每对节点之间的最短路径，这样：
如果x，y在路径中，v，那么路径，y是路径的子路径，v。我不知道一个算法或一个证明，实际上，我不知道这是否是可确认的。任何想法都是welcome.Thank你。
浏览 2提问于2016-07-04得票数 1
2回答
今天我遇到了这个词“单对最短路径问题”。我想知道对加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想，如果你想找到A和Z之间的最短路径，你绝对必须知道从A到B，C，D，……的最短路径。Y.如果你不知道后者，你就无法确定你的道路实际上是最短的。因此，对于我来说，任何最短路径算法都必须计算出图中从A到其他顶点的最短路径，才能得到从A到Z<em
浏览 4提问于2017-03-30得票数 10
回答已采纳
2回答
如果我们将图G反转到G‘，并从源顶点't’对G‘运行Dijkstra算法，这个算法会给出从所有顶点到G中't’的最短路径吗?有人能证明或找到反例吗？
浏览 6提问于2018-11-02得票数 0
诸如A* 100%之类的寻径算法可保证最短路径。但是我们可以手动分析图中给定的路径是否是最短路径吗？ 假设我们有这个加权图Weighted Graph 假设我们的起始节点是节点1，我们想转到节点2。我们采用的路径是节点1 ->节点2。显然，这是最短的路径。如果没有任何计算机，我们如何手动证明或确定这条路径是否是最短路径？
浏览 22提问于2021-10-30得票数 0
在“算法入门，第三版”练习24.3-5中，需要一个例子说明这是错误的(并不总是正确的)。这有可能吗？在我看来，这是不可能的，因为在通往当前停战的道路已经决定的时候，每个边缘都是放松的。逐字逐句地：
教授N.声称有Dijkstra算法正确性的证明。他声称Dijkstra的算法按照图中每条最短路径在路径上出现的顺序来松弛它们的边，因
浏览 6提问于2010-09-18得票数 13
回答已采纳
我被要求找出一种图，它的最短路径总数(使用Dijkstra算法)是指节点数。我想出了一个这样的图表：C->A'->B‘’(所有边的weight=1) C->B‘(重量= 2)
B‘-’>A‘-’-‘>B’>(重量= 2这样，Dijkstra算法找到的最短路径总数为Ω(2^(n/2))。我现在想弄清楚，它是否可以推广到Ω(
浏览 2提问于2012-10-27得票数 0
我正在寻找一种算法来找到两个URL之间的最短路径，或两个维基百科页面。(我不确定Dijkstra的是不是这里的</
浏览 7提问于2009-11-07得票数 4
在加权图中，如果要求计算最短路径.而且，任何两个节点都有可能有多个边，不同的权重将它们连接起来。应用弗洛伊德-沃尔算法或Dijkstra算法:如果两个节点之间存在多个边，我们是否可以取最小加权边而忽略其他边？
如果是的话，有人能证明吗？提前感谢
浏览 3提问于2013-06-15得票数 0
1回答
在Dijkstra算法中，我们计算路径长度以求最短路径。Dijkstra算法的正则版本将路径长度计算为到某个节点的权重之和，如果路径长度被计算为向上v +最大权的和，那么路径长度会怎样呢？但我该怎么证明呢？
我们将非常感谢你的帮助。
浏览 1提问于2014-01-17得票数 1
回答已采纳
2回答
根据算法书Corman的说法，Dijkstra只适用于所有边都具有非负权的图。这是否意味着，如果有任何负权重的边，它将不工作的整个图？还是不算负重边？请指出哪个是对的？
浏览 0提问于2013-08-09得票数 4
2回答
通过Dijkstra算法，我得到了一棵以源节点s为根并生成图G中所有节点V的最短路径树Ts=(s，V)，然后选择了最短路径树Ts=(s，V)的一个子树Tm=(s，K) (其中K是V的一个子集)，它只连接到所有V个节点中的K个节点，即子树Tm是最短路径树Ts的一个子集。我的问题是，现在我如何通过参数或引理/定理证明最短路径树Ts的子树Tm也是最短树？提前谢
浏览 2提问于2016-12-28得票数 2
2回答
我正在尝试理解A*，统一成本和贪婪搜索算法是如何工作的。我知道探索节点的方式在所有三种算法中都会发生变化(贪婪将基于启发式值进行探索，A*基于启发式加距离，均匀基于距离)。我想知道，对于给定的源和目的地，是否所有3种算法都应该提供最短路径(只需探索不同数量的城市？)或者他们能提供一条不同的路径。我最困惑的是实现部分-如果你将节点存储在队列中，那么当你打算探索目标节点时，你将拥有它的
浏览 4提问于2016-10-04得票数 1
1回答
q.peek().equals(endNode){ }
我见过的Dijkstra的每个实现都使用更早的实现，但当您知道结束节点时，后者使用的更快。
浏览 2提问于2014-05-28得票数 5
回答已采纳
1回答
我了解到Bellman算法的运行时间为O(x，E，x，E，V，V)，其中E是边的个数，V是顶点的个数。假设图没有任何负加权圈。我的第一个问题是，我们如何证明在迭代(每一次迭代检查E中的每一条边)中，它更新到每个可能的节点的最短路径，给定一个特定的开始节点？是否有可能我们已经迭代了很多次，但仍然没有得到到达每个节点的最短路径？
假设算法的<
浏览 2提问于2013-11-16得票数 3
回答已采纳
我知道普通的BFS搜索可以用来在无权图或边权相同的图中寻找最短路径，而Dijkstra应该用在加权图中，Dijkstra可以看作是BFS的变体。但我想知道，如果每次更新distw时，我都将节点推送到队列中，而不是在普通的BFS搜索中只推送一次，那么这个算法是否适用于寻找最短路径？我在一个leetcode问题上尝试了这个算法，它是有效的，但是leetcode问题只检查有限的测试用例，所以我不能证明这个
浏览 36提问于2020-12-10得票数 0
回答已采纳
我有一个家庭作业，我要找出两个城市之间最便宜的机票，考虑到中途停留。DijkstraAlgorithm(weighted simple digraph, vertex first)
我很难理解的是--尤其是在看整个伪代码的时候--为什么它只接受一个顶点作为参数我需要找到两个顶点之间最便
浏览 4提问于2011-12-05得票数 2
回答已采纳
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i = 1 to n:
for j
浏览 8提问于2021-02-22得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
