1回答
如何在没有权重的DAG中找到最长路径？
我知道如果DAG是按拓扑排序的，那么从A到B的最长路径可以在线性时间内找到，但我需要在所有图中找到最长路径。有没有比搜索所有顶点对之间的最长路径(即O(n^3))更快的方法？
浏览 0提问于2013-04-07得票数 1
回答已采纳
我正在寻找一种方法来扩展BFS方法，用于在无权有向图中找到单源最短路径，并在O(N+M)时间内解决上述问题。其中N是顶点数，M是边数。
收缩图的顶点，在它们之间有一个边权0。但是，这肯定是错误的，因为那时我将改变图的属性，并向原本没有任何属性的顶点添加新的边。将边权值改为1和2，然后在长度为2的路径中创建虚拟顶点，将这些边转
浏览 1提问于2014-02-02得票数 8
回答已采纳
1回答
我们知道，寻找两个顶点之间的最大权重路径是np困难的。但是如果我们限制边权重，例如。所有的边权重都小于某个特定值x。我清楚地定义了下面的问题。我有一个有向图G(V，E)，其中每条边的权重都在1到|V|之间。我想找到两个顶点u和v之间的最大权重路径</
浏览 1提问于2018-03-11得票数 0
1回答
改进Dijkstra算法
、、、、
给出了一个边权W介于0~ 1之间的有向图。从源到目标节点的路径代价是路径上从源到目标节点的边权的乘积。我想知道一种算法，它可以在多项式时间内或使用任何其他启发式方法找到最小代价路径。我认为沿着取边权的对数值(取模值)，然后对这个图应用dijkstra，但认为会有无法计算的精度问题。
还有其他更好的方法吗?或者我可以改进日志方法。
浏览 0提问于2016-11-07得票数 1
1回答
我有一个问题，那就是给出了一个具有正权的无向图。有N个顶点，我需要从vetex 1到N的所有可能路径中获得路径中两个顶点之间的最大权重的最小值。但是，这些可能路径的总权重不能大于T。我意识到这是一个极大极小路径问题，所以我可以从图中构造一个最小生成树，然后从那里，我可以得到路径的</e
浏览 19提问于2019-02-24得票数 1
4回答
给定一个有向图G=(V,E)，两个顶点s，t和两个权重函数w1，w2，我需要在<代码>D10</代码>从s到t的所有最短路径中找到w2到s的最短路径。首先，如何找到两个顶点s和t之间的所有最短路径？Dijkstra的算法帮助我们找到从一个顶点到每个其他可访问顶点</em
浏览 0提问于2013-05-11得票数 4
有一个具有正权重边的有向图G，我们将路径的成本定义为具有最小权重的边和最大权重的边之间的差异。目标是在其他路径中找到一条代价最大的路径。我们不需要返回路径本身，只需要返回最大开销。如果x是顶点数，y是边数，那么x < 10^5和y < min(x
浏览 30提问于2020-12-02得票数 2
回答已采纳
1回答
我正在尝试通过在MST中添加一个新顶点来更新MST。为此，我一直在关注Chin和Houck的“更新生成树”。
论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间所有可能的路径，然后从路径中找到最大的边。我一
浏览 0提问于2012-07-16得票数 0
回答已采纳
1回答
假设我们有一个有n个顶点的完整图。每个顶点都有一个值。两个顶点i和j之间的边的权重等于valuej _i_ xor _valuej_j。问题是找到一条从顶点1到顶点n的路径，该路径中边的权重最大是最小的。我已经修改了Dijkstra的算法，找到了一个O(n
浏览 0提问于2013-06-29得票数 4
回答已采纳
1回答
我只需要一个想法，如何在一个加权有向图中找到两个顶点之间的所有最小代价行走。我不知道有什么算法能做到这一点。我正在考虑用和算法找到最低成本的步行，然后修改顶点的权重，这样如果我再次运行它，它将被迫给我另一条路径。但是，如果新的步行使用将被修改的边缘，则这将无法工作。
浏览 4提问于2013-11-26得票数 2
回答已采纳
1回答
例如:给出一个具有N个顶点和N条边的简单连通图G(简单图是一个无向图，它没有环，并且在任何两个不同的顶点之间不超过一条边)。很明显，图G只包含一个圈，您可以假设这个圈的长度是奇数(这个圈中有奇数个顶点)。顶点的编号从1到N。每条边都被指定了相应的整数权重。您的任务是刺激两种类型的查询:更新由f u v表示的查询:将最短路
浏览 0提问于2013-05-11得票数 2
假设我有这样一个，其中从每个节点(除了最下面一行的节点)到它下面的两个节点都有一个有向边： 3 8 2 7 4 4我需要找到一条通过这个DAG的路径，其中节点的权重之和是最大化的。您只能从此树中的节点沿对角线向下-向左或向下-向右移动。因此，例如，7，3，8，7，5将给出此树中的最
浏览 1提问于2012-02-06得票数 7
回答已采纳
1回答
假设我有一个有向图，每个节点上都有权重。任意两个节点之间的路径权重定义为:路径中所有节点的和，并乘以该路径中的节点数。
我们想要找到一个顶点不相交的路径覆盖，它具有覆盖中所有路径的最大权重和。有没有解决这个问题的算法？还是有什么问题可以归结为这个问题呢？
浏览 1提问于2016-11-18得票数 0
回答已采纳
2回答
无向图中的是两个顶点v，w之间的一条路径，它最小化了路径上边的最大权重。设T是给定图G=(V，E)的最小生成树.如何证明，对于V中的任意一对顶点v，w，在v与w之间总是存在一条完全在T上的极小极大路径。
我试图假设T上没有完全的极小极大路径，但我不知道如何得到一个矛盾。
浏览 0提问于2017-03-25得票数 3
回答已采纳
我正在写一篇关于一些图形算法(CPM中使用的)的文章，我需要一些算法的名称，它可以找到DAG中的所有关键路径。我看过弗洛伊德-沃尔算法，我不知道它是否能帮助找到DAG中的所有关键路径。如果临界路径和最长路径是相同的，那么Floyd算法可以通过在图中寻找所有最长而不是最短的路径的方式进行修改。即使它可以被修改，是否有更好的
浏览 12提问于2013-08-26得票数 1
回答已采纳
给定一个有向无环图G和两个顶点u和v，我需要在G中找到最长的u-v路径。DFS调用explore函数在visited[]布尔数组中存储访问过的顶点(如果顶点被访问，则数组中的值设置为真，否则为假)。顶点u和v永远不会标记为已访问。变量MAX存储最大路径；当在explore()函数中到达停止顶点时，将max设置为当前路径长度的<e
浏览 18提问于2019-10-06得票数 0
回答已采纳
int表示从源节点到目标节点的最小移动次数。总而言之，它是一个对的列表，其中第一个元素是由Source和Destination组成的对，第二个元素是它们之间的最小距离。-> DISTANCE)((1,1 to 2,2) -> DISTANCE)
((1,1 to 3,3) -> DISTANCE) 我试图实现的是计算将一些东西从所有来源移动到可用的目的地所需的最小移动因此，
浏览 29提问于2018-12-26得票数 0
回答已采纳
1回答
给我一个有向图，它的权重分配给顶点，而不是边。我的目标是在这个图中找到路径的最大权重。一条路径的权重是它包含的所有唯一顶点的权重之和。一个顶点可以在路径上被多次访问，尽管它只计算一次。重建路径是不必要的。
由于图的大小，它
浏览 1提问于2016-01-26得票数 2
1回答
沿路径的最小边权重
、、、、
如何在任意顶点之间的所有可能路径上找到一组最小边权重的最大值(u,v)i.e.Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9Path 2: s - x - y - z - w - t withweights 3 - 9 - 8 - 6 - 7因此，结果是max(1,
浏览 2提问于2012-05-21得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
