我目前正在解决一个问题，这个问题需要我找到一个有向加权图的中心。我正在努力确保我对一些相关概念的理解是正确的。例如，假设我们有一些节点集表示为链接：/wiki/Braess%27_paradox
/wi
浏览 1提问于2017-06-03得票数 2
回答已采纳
1回答
给定一个有向赋权循环图，并且m(x，y)给出的顶点之间的最小路径距离，找到最小化m(a，v) + m(b，v) + m(c，v) +…的顶点v。对于n个顶点a，b，c...例如，如果图是无向的，并且我们想要具有到顶点a和b的最小路径的顶点v，那么v就是从a到b的最小路径中心的顶点。我<
浏览 11提问于2018-09-04得票数 2
给定一个具有N个顶点的无向赋权完全图G=(V,E)，我想知道寻找具有M个顶点(M <= N)的最小完全子图(具有最小边权和)是否是NP难的。
浏览 111提问于2021-03-26得票数 0
1回答
赋权有向图的邻接矩阵
、、、
A)设A是具有n个顶点的赋权有向图G的邻接矩阵，其中A[i,j]是边i到j的权重。如果没有这样的边缘A[i ,i]=0。矩阵A^K= A*A*A*...A。如果我们使用+而不是*，并且使用min而不是+，则时隙A^k [i,j]不能用至多k边来描述路径i到j的权重。我想找出这个问题表现出什么东西？B)设A是具有n点的赋<
浏览 3提问于2014-10-18得票数 0
给定一个无向赋权图G(V，E)。求G的一个顶点x，使得dist(u，x) + dist(v，x) + dist( w，x)是最小的。X可以是G中的任何顶点(包括u、v和w)。对于这个问题有什么特别的算法吗？
浏览 2提问于2016-08-01得票数 2
设G= (V，E)是不含负圈的有向赋权图。如何修改福特bellman算法，使其在while循环的m+1次迭代后停止。M是最小路径中的最大弧数(根据权重而不是道路中拱门的数量确定的最小道路)
浏览 6提问于2020-07-03得票数 0
1回答
给定一个包含许多节点的无向赋权图，如何计算所有对最短路径的一个子集？Dijkstra或Floyd-Warshall都可能会计算额外的节点，这对于我的应用程序来说可能
浏览 0提问于2017-06-13得票数 5
2回答
我很难理解Skeina算法中检测有向或无向图中循环的所有内容 // if parent[v] == y it means we're考虑到v是个邻居我们刚刚发现了它？
我混淆了对parentv !== y的检查，但是在无权图的情况下，我想这是有意义
浏览 2提问于2015-02-20得票数 3
回答已采纳
1回答
给定一个赋权完全二部图G=(V，U，E)，最大赋权二部匹配问题，即指派问题，目的是在G中寻找一个边权和最大化的匹配。我知道有一些方法(例如匈牙利算法)可以解决这个问题。现在，我想解决一个稍微不同的问题：
给定一个加权完全二部图G=(V，U，E)，我想同时找到G中的最大加权二部匹配和第二大加权二部匹配。任何想法都将不胜感激。
浏览 7提问于2019-08-12得票数 1
2回答
无向图抽象
、、
我有一个无向加权图，我需要正式地描述它。通过自动机或标记转换系统的抽象似乎没有为无向图定义，只覆盖了有向图。图中的状态相互依赖，但是方向本身并不相关。你知道什么数学模型可以用来形式化地描述这样的图吗？
浏览 0提问于2017-01-29得票数 1
1回答
最小生成树与生成树的区别
、、、、
我一直在阅读生成树的概念及其类型。这就是我所理解的：最小生成树：是一种生成树，其边权之和最小。这是否意味着，在检索MST时，
如果我们在G中遇到一条边较多的路径(与其他路径相比)，但在边权之和上的权重最小(与所有其他路径相比)，我们就不会把它当作MST了吗？当G有</em
浏览 3提问于2020-05-02得票数 0
回答已采纳
1回答
作为学校作业的一部分，我需要在带警告的加权循环图上实现Dijkstra的算法--在每条边上都存在一个次要权重/成本(此后称为B)，算法是在保持总B在一定恒定值的同时，从源节点到目标节点的最短路径。在基本Dijkstra的基础上，我在松弛/更新条件中增加了一个附加条件，即当前最短路径必须在给定的常数B值之下。neighbour node is less than input **B** value:
浏览 12提问于2022-09-17得票数 0
回答已采纳
假设我有一个简单的有向非负赋权图G= ( V，E)和一个顶点子集X⊂V。图是邻接表表示，子集X是列表。我如何找到一个算法来计算不属于X的图中顶点s，t之间的最短路径，以及当路径使用X中的两个顶点时，这两个顶点之间至少有一个不在X中的顶点？该算法应该在O(m+nlogn)时间内。我已经考虑这个问
浏览 12提问于2020-05-10得票数 0
回答已采纳
1回答
如何计算循环图的密度？
、、、、
我在寻找有向循环图的密度。据称，
2 *\x{e76f}\x{e76f}
一个简单的图，而不是多个图，是一个无向图，其中多个边和循环都是不允许的</e
浏览 11提问于2016-11-30得票数 0
回答已采纳
1回答
两天前，我有个测试。这就是问题之一。选择图形的类型。
答案是5，但我想答案也是1。1是对的？或者5是对的？或者1和5都是对的
浏览 2提问于2013-12-19得票数 1
回答已采纳
4回答
最小生成树与最短路径树的区别
、、、、
下面是一个练习：(a)无向图的最小生成树中一对顶点之间的路径是否必然是最短(最小权重)路径？
(b)假设图的最小生成树是唯一的。无向图的最小生成树中一对顶点之间的路径必然是最短(最小权)路径吗？我<e
浏览 14提问于2012-05-04得票数 17
回答已采纳
1回答
改进Dijkstra算法
、、、、
给出了一个边权W介于0~ 1之间的有向图。从源到目标节点的路径代价是路径上从源到目标节点的边权的乘积。我想知道一种算法，它可以在多项式时间内或使用任何其他启发式方法找到最小代价路径。我认为沿着取边权的对数值(取模值)，然后对这个图应用dijkstra，但认为会有无法计算的精度问题。
还有其他更
浏览 0提问于2016-11-07得票数 1
2回答
设G= (V，E)是赋权连通无向图，T是最小生成树。设e是不在E中的任何边(并且具有权重W(e))。证明或反驳:T U {e}是包含G‘= (V，E U {e})的最小生成树的边集。嗯，对我来说这听起来是真的，所以我决定证明这一点，但我每次都被卡住了……
例如，如果e是具有最小权重的新边，谁能向我们保证T中<e
浏览 2提问于2013-02-26得票数 7
回答已采纳
3回答
博鲁夫卡算法()是否只适用于无向图？例如，如果我们有一个图结构，如下所示：那么最小生成树应该包括边：然而，Boruvka的算法会吐出1 -> 2
浏览 1提问于2012-12-11得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
