只是需要确认一下:当我在图上运行Dijkstra的算法时，在最后我会有一个生成树，对吗？(不一定是最小生成树)谢谢
浏览 11提问于2014-02-12得票数 0
回答已采纳
1回答
显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。
浏览 58提问于2019-02-05得票数 2
1回答
我很难找到Dijkstra最小生成树的示例算法。我已经知道Dijkstra的单最短路径算法，但不知道生成树。我在课堂上有一个简单的解释，就是：
我可能需要为自己编写代码，但我想我会问是否有人有一个好的例子。
有人能帮忙吗？
浏览 0提问于2018-04-08得票数 4
回答已采纳
5回答
它能用来找出最小的吗？如果是这样的话，是怎么做的？
编辑:这不是家庭作业，但我正在尝试理解一个旧的练习考试中的一个问题。
浏览 5提问于2009-12-16得票数 20
回答已采纳
我正在寻找一些常见数据结构和算法的标准实现，如：
我本来希望有一个Apache通用的-XXX包，但可惜没有？
浏览 0提问于2012-11-13得票数 0
回答已采纳
3回答
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
浏览 1提问于2013-06-27得票数 6
1回答
给定一个有向加权图G=(V，E)，运行Dijkstra算法可以产生多个具有不同权重的最短路径树as seen in this picture，其中A是源，D是目标。如何创建一个在运行Dijkstra算法(O(V+E)logV)的同时返回总权重最小的Dijkstra树的算法？
浏览 13提问于2020-07-29得票数 0
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。
浏览 1提问于2012-11-08得票数 0
我想知道对于dijkstra和prim的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。
例如
浏览 1提问于2010-04-28得票数 5
2回答
我需要从A开始，到G，所以最小生成树必须在这些点之间绑定。我们应用程序中的约束之一是，从A开始到以G结尾的间隔必须完全覆盖(没有空白)。我在看，不知道如何指定A和G必须是起始点和端点。想到的其他一些问题是：
注意，区间F有一个唯一的区域。因此，我的最小生成树可能应该只连接A，而不是A。是否有一个标准的方法，给定一个较大的图
浏览 9提问于2015-02-04得票数 2
回答已采纳
1回答
考虑从加权连通图G中寻找边的最小权连通子集T的问题。T的权重是T中所有边权的和。(a)为什么这个问题不仅仅是最小生成树问题？提示:考虑负权重边缘。(b)给出了一个计算最小权连通子集T的有效算法。(c)来自Sciena手册
(a)生成树最小化汇总树权重，但minimum weight connected subset -每对路径权重，因此我们可以重用相同的负边来减少每对路径？(b)关于额头的决定:运行dijks
浏览 1提问于2011-01-27得票数 3
1回答
将Dijkstra/Prim最小生成树算法(不是最短路径)应用于以下图(从顶点a开始)。
我不太确定如何开始填写这些图表。这是一个考试练习的问题，所以我想学习并理解它。
浏览 2提问于2013-11-21得票数 0
1回答
我们希望找到与s最小距离树(即在s上运行prim/dijkstra获得的最小距离树)不同的最便宜最小生成树的总成本(定义为所有边的权重之和)。
对于r中的每个顶点v，运行一个bfs遍历g中的所有边缘g：并找到不存在于r中的e&#
浏览 2提问于2015-12-27得票数 1
我知道这两个算法用来解决不同的问题，dijkstra算法是用来在图中寻找最短路径，而kruskal算法是用来寻找graph.But的最短路径，它们是如此相似？它们之间是什么关系？
浏览 1提问于2013-06-21得票数 0
回答已采纳
我有一个由最小生成树表示的边权重无向图。每个顶点都由一个整数表示。MST如下所示：
我想知道，如何使用这个MST来找到从顶点x到顶点y的最短路径？
浏览 6提问于2019-10-06得票数 0
云服务器
ICP备案
云直播
对象存储
实时音视频
腾讯云开发者
