1回答
S是最短路径树(不一定是G的防止小组委员会)。因此，我要设计一个算法来检查图S是否是图G的最短路径树。在G和S上运行Dijkstra算法(返回图，而不是最短路径)。检查每个顶点的dist(v)值，如果它们都是相同的，则S是G的最短路径树。
我不知道这个算法是否有效，但我认为它是合理的。如果它是真的，我如何证
浏览 3提问于2014-02-24得票数 1
回答已采纳
3回答
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
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回答
如果我知道给定的图实际上是一棵生成树，即每一对顶点之间只有一条路径，那么如何才能找到从每个顶点到每个顶点的最短路径？我想要最理想的解决方案。我知道Dijkstra的算法，但它非常复杂。我基本上想知道每个顶点从一个源的距离和路径。考虑到它是一棵生成树，那么它的最佳和最优解是什么？另外，如果图实际上是生成树，那么请告诉我是否有什么不同的方法可以找到所有对最短路径，而不是多次使用单源最短路径</e
浏览 6提问于2014-12-11得票数 0
回答已采纳
2回答
Dijkstra的最短路径算法会在具有负权边的有向树上返回正确的结果吗？
在具有负权重的一般图上，该算法将失败，但由于它是一棵有向树，因此感觉该算法会成功。
浏览 5提问于2022-06-01得票数 2
1回答
我有一个对称的图，并创建了一棵树，其中包含从随机顶点到任何其他顶点的所有最短路径。是否可以使用树构建最小生成树(MST)？我的算法类似于深度优先算法。
浏览 1提问于2013-07-06得票数 0
回答已采纳
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
1回答
给定一个有向加权图G=(V，E)，运行Dijkstra算法可以产生多个具有不同权重的最短路径树as seen in this picture，其中A是源，D是目标。如何创建一个在运行Dijkstra算法(O(V+E)logV)的同时返回总权重最小的Dijkstra树的算法？
浏览 13提问于2020-07-29得票数 0
3回答
有没有一种图算法，在给定起点(V)和终点(U)的情况下，可以找到通过给定的一组边的最短路径，但如果u是不连接的顶点，它还会确定添加缺失边的最短路径，直到u不再断开为止？我可以有一个像素矩阵森林，比如说7棵左右的黑色像素树。我需要找到每棵树的真实端点，找到每棵树的最短路径，然后将所有倾斜树合并在一起形成一条线(即从原始矩阵中最远的两个端点开始的一条最短路径)。
浏览 3提问于2009-08-23得票数 1
3回答
请推荐资源，了解如何使用Prim算法和Bellman-Ford算法在有向图中找到最小生成树，以计算有向图中的最短路径。
浏览 0提问于2010-12-20得票数 0
3回答
我发现了许多关于寻找最短路径或问题的最佳/最佳解决方案的算法和方法。然而，我想要做的是一个算法，它能找到从一个点到另一个点的前K-最短路径。我面临的问题更像是在树中搜索，在每一步中都有多个选项，每个选项都有其权重。面对这类问题，使用了什么样的算法？
浏览 3提问于2010-11-19得票数 1
3回答
对于每个查询，我们必须找到从源S到目的地D的最短路径，假设原始图中没有边(x，y)，如果从S到D没有路径，则必须打印No。如何有效地解决这个问题？，直到现在，我所做的是实现简单的Dijakstra算法。
对于每个查询q，每次我都将(x，y)分配给Infinity，并找到Dijakstra最短路径。
浏览 5提问于2012-06-05得票数 10
回答已采纳
1回答
如何构建生成树(解决方案可能不是唯一的)，以便最小化所有节点的深度总和？这显然不是寻找最小生成树，因为边的“权重”实际上取决于孩子的深度。我认为，给定一个指定的根，深度和最小的树可以通过贪婪地将所有可以连接的子节点以广度优先的顺序连接到每个节点来形成。因此，我将通过应用相同的程序N次，指定N个节点中的每个节点作为根，并从N个候选节点中选择最小的一个，来找到总深度最小的树。这是一个有效的算法吗？如果它是错误的，或者是否存在更有效的方法，请指出。
浏览 8提问于2013-02-22得票数 8
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。附注：我很难证明MST包含每个顶点的有向图的最短路径。
浏览 1提问于2012-11-08得票数 0
1回答
最小生成树与最短路径树
、、、
有没有可能在一个无向图中有一个没有公共边的MST，并且在一个无向图中有最短的路径树？
我一直试图举出不同的例子，但这似乎是不可能的。最短路径树中的最短路径边似乎也应该包含在MST中。
浏览 1提问于2016-03-10得票数 1
用递归树解释: T( n) =T(n/3)+T(2n/3)+cn的解，其中c是常数，是Omega(n lg N)最短的路径将是最左边的路径，因为它以最低的值运行，而最右边的路径将是最长的，这意味着树是不平衡的。最短路径可定义为:n -> 1/3n -> ( 1/3 )^2n->.&g
浏览 2提问于2015-01-22得票数 1
回答已采纳
我认为当使用dijsktra算法时，每个路由器的最短路径树可能不同.在链路状态路由中，所有路由器都具有相同的网络拓扑结构.
因此，每个路由器是否都有其他路由器的地图(最短路径树)？
浏览 0提问于2022-02-23得票数 2
回答已采纳
运行SPF，以找到所有可能的路径通过该地区的拓扑，从自身到每个网络。
计算每个路由中所有传出接口的OSPF接口成本，选择每个网络的最低总成本路由作为最佳路由。我的问题是:找到所有可能的路径是SPF算法的函数之一吗？我认为所有可能的路径都是由LSDB隐式显示的，SPF算法的任务就是创建一个SPF树，并得到该树中每个网络的最短路径。或者在这里，作者想表达SPF穿越所有可能的路径并找到最短路径</
浏览 0提问于2017-01-24得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
