我有一个N x M矩阵，我有一定数量的源和汇，我需要找到它们之间不相交的最大路径，基本上两条路径不能使用相同的顶点。为了确保这一点，我已经将所有顶点的所有最大容量设置为1。我已经尝试将BFS算法与Ford-Fulkerson算法相结合，使用连接到所有源的超源和由所有汇点连接的超链，但它并不总是返回正确数量的最大
浏览 19提问于2020-05-12得票数 0
回答已采纳
我有一个要实现的算法，它可以在图中找到最长的路径/s。然后查找与前一条路径/s没有任何共同关系的下一个最长路径/s，直到整个图被表示为不相交的路径。它们在所包含的关系上是不相交的，但在它们连接的地方会有重叠的节点。我希望这些关系中的每一条不相交<
浏览 4提问于2015-05-07得票数 0
回答已采纳
1回答
我试图使用路径在SVG中呈现一个简单的纽结，尽管我不承诺在任何其他SVG元素上使用路径。我遇到的困难是显示纽结的重叠，因为SVG元素倾向于相交。我在下面列出了两次失败的尝试，第一次说明了交叉问题，第二次克服了它，但是新的问题--线不连续(现在拐角处有重叠)。我怎样才能继续下去，使渲染的图像看起来像是一个连续的链，并使重叠/相交的
浏览 0提问于2015-08-14得票数 1
回答已采纳
2回答
是否有一个确定性的算法来检查一个图是否包含一个从源到目的地的顶点不相交的路径，具有复杂性O(nm^2) (n是顶点数，m是边数)，还是这个NP-硬(如果是，为什么)？顶点不相交路径是指没有公共内部顶点的路径。例如：s -> x -> y -> z -> ds -> a -> b ->
浏览 4提问于2013-05-01得票数 2
回答已采纳
1回答
我们有一个有向图(无权) G(V，E)，具有两个顶点s和t，使得s的内度和t的出度等于0。我们希望找到从s到t的最大多条不同的边路径.通过使用哪种算法，我们可以做到这一点。
浏览 4提问于2015-03-17得票数 0
回答已采纳
1回答
如何在有向图中找到边不相交路径的最大数目。该图是未加权的。假设图是这样的：因此，图中有两条边不相交的路径：4->1->2和5->1->3我的问题是。如果我在一个节点上设置了一个“守卫”，它就可以从那个节点开始它的旅程。守卫可以多次访问任何城市，甚至是其他守卫已经访问过的</em
浏览 2提问于2012-09-30得票数 0
回答已采纳
1回答
我正在绘制一个由许多线组成的大方案。我是在UIView的drawRect:方法中完成的。该方案大于视图层，我检查每条线，只有当它与可见矩形相交时才绘制它。但在某个时刻，我想，我应该这样做吗？所以问题是:当我使用函数CGContextAddLineToPoint()时，Core Graphics是测试这条线是否与layer rect相交，还是只是绘制它？
浏览 3提问于2010-04-02得票数 1
回答已采纳
1回答
我需要在下面的图中计算从A到B的两条路径，约束条件是这些路径不能共享任何边： 嗯，好吧，不能上传图片，这是个link。 所有的边都有正权重；对于这个例子，我认为我们可以假设它们是相等的。我的简单方法是使用Djikstra的算法来计算第一条路径，如上图中的第二张图所示。 然后，我从图中删除边，并尝试计算第二条路径，但失败了。有没有Djikstra，Bellman-Ford (或其他任何东西)的变体，可以计算上面第三张图
浏览 0提问于2010-05-11得票数 0
在最大二部匹配的Hopcroft-Karp算法中，为什么我们总是在广度优先搜索中寻找最短的增广路径？是不是因为广度优先搜索总是找到最短的路径？我只是搞不懂为什么增强路径是最短的，这很重要。
浏览 2提问于2013-05-15得票数 0
回答已采纳
1回答
给出了G= ( v，E)中的两个顶点u和v和一个正整数k，描述了判定从u到v是否存在k个边不相交路径的算法，如果这个问题的答案是肯定的，描述如何计算一组k边不相交路径。解:运行从u到v的最大流(给图G中的所有边以1的权重，使一个边只能是从u到v的一条路径的一部分)并得到流的值
浏览 1提问于2016-04-27得票数 3
1回答
在研究另一个问题的时候，我偶然发现了这个问题：
还钱。为了解决这个问题，我尝试了一种递归方法，在这种方法中，对于每
浏览 1提问于2018-09-21得票数 2
回答已采纳
所以我有一个n x m矩阵。我需要找出有多少种不同的方法可以在这个矩阵上放置k不相交的路径。每条道路都满足了以下条件：最后一个是-Ends。-If路径结束于(a,b) for b<m，然后下一步只能在网格(a',b+1)上完成，其中|a'-a|<=1 (意味着我向下移动一步，元组中的第一步是x坐标，第二步是y坐标)。-I知道n很小(比如8)，所以它不会破坏算法的
浏览 0提问于2014-03-03得票数 2
回答已采纳
1回答
在这里，我试图断开一个图中的两个顶点，并尽可能减少边缘去除。如果有什么具体的算法吗？本文提出了用最大流最小切问题来解决这一问题的一些建议，但还没有得到将这个问题转化为最大流最小切定理的一般想法。在这个过程中，我可能最终会删除F和G之间的一个边缘，这是无用的。
浏览 0提问于2016-05-08得票数 12
回答已采纳
很多类似的问题都被问到了，但没有完全解决我的情况:在一个简单的无权图和一个整数k中，给定两个顶点，我如何才能在顶点之间找到所有k元组的边-不相交的路径？(特别是，我感兴趣的是，k是起始顶点的外部度。)
我知道Suurballe的算法会给我k条边不相交的路径，但它会(不确定地)解决一个问题，而不是给我所有的解决方案。像Edmonds这样的最
浏览 4提问于2020-07-30得票数 2
回答已采纳
1回答
假设存在从源到目的地的工作路径，该工作路径携带包含数据的分组并使用某些资源(它所经过的链路的一定量的带宽)。对于每个源和目标，我必须提前同时建立一条工作路径和一条保护路径，以防链路故障，但它们必须是链路不相交的。如果链路1-2发生故障，我必须通过预先建立的保护路径发送数据包，该保护路径与工作路径不相交。例如，我
浏览 3提问于2018-06-20得票数 1
1回答
，(xn，yn) }的集合，找出具有以下性质的最短路径：
我假设每个点只能访问一次(但我不确定它是否来自上述属性)。extend path that has last
浏览 1提问于2014-08-28得票数 2
回答已采纳
2回答
在网格中查找路径时出错
、、、、
我试图在跳棋板上找到左上角和右下角单元格之间的路径数。我只能移动到相邻的右边和相邻的底部单元格。这样，我最多可以有2条不相交的简单路径。我使用的是递归方法。} return true;}
但是有了这个代码，我只能遍历下三角矩阵当我反转遍历()函数中if块的
浏览 3提问于2013-11-24得票数 0
1回答
我试着用QPainterPath创建两种形状的结合来画一个漫画气球：QRectF br = text_->boundingRect().adjusted(-kb,QPainterPath pRect;我得到的是：鉴于我想要得到一个单一的形状，只有一个连续的轮廓，如下：我怎么才能解决这个问题？
浏览 0提问于2018-05-11得票数 0
回答已采纳
1回答
任意两个节点之间的路径权重定义为:路径中所有节点的和，并乘以该路径中的节点数。我知道这是NP问题。有没有解决这个问题的算法？
浏览 1提问于2016-11-18得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
