Suurballe的算法是寻找源-目的地对的k条不相交的路径，但现在，我有一个问题，目的地不是单一的。例如，我想找出从节点'A‘到节点'B'，'C'，'D’的k (K>=3)条不交路径，如何解决这个问题？
顺便说一句，我可以从哪里得到关于Suurballe算法<e
浏览 9提问于2017-03-06得票数 1
让我们考虑一下这张图：假设我想要第一条路径，源为A，目的地为H，第二条路径以源为A，目的地为D。
我无法应用suurballe算法，因为它只适用于同一源和相同目的地的路径。期望O/p为第一路径=>，第二路径为=> Expected。这两条是顶点不相交的路径。在这种情况下，如何计算两个顶点不<em
浏览 1提问于2022-05-31得票数 2
回答已采纳
2回答
我感兴趣的是采用Suurballe的算法来找到从源到目的地的最佳K个路径，而不仅仅是两个最佳路径。我认为人们一直都在这么做，但我已经搜索了几个小时，也找不到一篇能清楚解释这一点的论文。在Suurballe的wikipedia页面上有一篇关于它的论文的引用，但它没有给出前两个扩展的细节(如何修改图形和合并结果等)。顺便说一句，我实际上是在研究顶点不相交问题，而不是维
浏览 1提问于2013-08-20得票数 1
2回答
是否有一个确定性的算法来检查一个图是否包含一个从源到目的地的顶点不相交的路径，具有复杂性O(nm^2) (n是顶点数，m是边数)，还是这个NP-硬(如果是，为什么)？顶点不相交路径是指没有公共内部顶点的路径。例如：s -> x -> y -> z -> ds -&g
浏览 4提问于2013-05-01得票数 2
回答已采纳
1回答
我得到了一个图，G= (V，E)，它是正权的，有向的，无环的。我要设计一个算法，运行在O(k(m + n))内，用于报告从s到t的k边最短路径。k边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，路径的总权重也必须是最小的</e
浏览 0提问于2013-03-14得票数 1
在最大二部匹配的Hopcroft-Karp算法中，为什么我们总是在广度优先搜索中寻找最短的增广路径？是不是因为广度优先搜索总是找到最短的路径？我只是搞不懂为什么增强路径是最短的，这很重要。
浏览 2提问于2013-05-15得票数 0
回答已采纳
我正在开发一个跨平台(iOS和安卓)的应用程序，它要求用户遵循一条由几个目的地组成的(可能是封闭的)路径。到目前为止，我最好的选择似乎是找到一种方法来打开谷歌地图，网址如下：有没有办法在Google
浏览 0提问于2016-12-07得票数 0
我负责一个网站，让人们联系金融专家，根据您的需要。因此，我为每个可能的路径创建了一个不同的目标。目的地是相同的，但漏斗是不同的，取决于用户是否检查专家的个人资料之前，他说，他想要与他是
浏览 0提问于2018-02-02得票数 1
回答已采纳
我需要确保一个点与从多个其他点派生的直线之间的距离不超过x。棘手的部分是我有点，而不是一条线…(这条线是隐含
浏览 1提问于2015-03-12得票数 0
1回答
该解决了块图或二部置换图的最优路径覆盖问题。在导论的第三行中，提出了最优路径覆盖问题是NP-完全问题，并提到了“计算机与难处理:大卫·约翰逊( David S.Johnson )的NP-完备理论指南”。但我在书里找不到它的证据。如果有人知道如何证明这个问题的NP-完整性，那么分享您的解决方案。最优路径覆盖问题：
给定一个图G，找到一个最小数目的顶点不相交路径，这些路径集合在一起覆盖
浏览 3提问于2016-11-30得票数 0
回答已采纳
1回答
后台：我有一个节点集合，它表示产品在流程中移动时的交集。这些节点被连接成有向图。有几个独立的图，因为乘积并不总是相交的。我们能够编译一个期望的初始源的列
浏览 2提问于2011-12-13得票数 0
回答已采纳
1回答
给出了G= ( v，E)中的两个顶点u和v和一个正整数k，描述了判定从u到v是否存在k个边不相交路径的算法，如果这个问题的答案是肯定的，描述如何计算一组k边不相交路径。解:运行从u到v的最大流(给图G中的所有边以1的权重，使一个边只能是从u到v的一条路径的一部分)并得到流<e
浏览 1提问于2016-04-27得票数 3
很多类似的问题都被问到了，但没有完全解决我的情况:在一个简单的无权图和一个整数k中，给定两个顶点，我如何才能在顶点之间找到所有k元组的边-不相交的路径？(特别是，我感兴趣的是，k是起始顶点的外部度。)
我知道Suurballe的算法会给我k条边不相交的路径，但它会(不确定地)解决一个问题，而不
浏览 4提问于2020-07-30得票数 2
回答已采纳
1回答
在一个有循环和负边的无向图中，使用BFS (使用遍历的最小顶点)在O(log )时间内找到目的地是可能的吗？例如:给出一个具有N个顶点和N条边的简单连通图G(简单图是一个无向图，它没有环，并且在任何两个不同的顶点之间不超过一条边)。您的任务是刺激两种类型的查询:更新由f u v表示的查询:将最短路径上所有边的权重的</e
浏览 0提问于2013-05-11得票数 2
2回答
我有一个二维的阶矩阵(M )，其中所有的单元格都包含0，除了K个特殊的单元格，其中包含一个特殊的值，比如1。现在，我需要从单元格say (0，0)开始，到达单元格(M-1，N1)。现在，我需要在(M-1，N1)单元的每一个成功到达的地方找到，我收集了多少个特殊值，它们的频率是多少？例:我可以说3条路径只包含一个特殊值，我有10条路径包含2个特殊值.诸若此类。我需要打印所有可能的对<
浏览 2提问于2015-09-20得票数 1
如果我想绘制两条彼此相交的非不透明线，你会在它们相交的区域中得到一个更高不透明度的区域：plt.plot([0, 0], [-1, 1], 'k-', lw=10, alpha=0.5, zorder=1)
plt.show()
浏览 1提问于2020-04-24得票数 4
1回答
我们有一个有向图(无权) G(V，E)，具有两个顶点s和t，使得s的内度和t的出度等于0。我们希望找到从s到t的最大多条不同的边路径.通过使用哪种算法，我们可以做到这一点。
浏览 4提问于2015-03-17得票数 0
回答已采纳
我有一个具有一个源路径和两个目标路径的文本文件。我正在将它们发送到一个名为Copy(源，目标)的函数中。对于它创建的一条路径(目的地)，.I想要发送另一个参数(其它目的地路径)...How，我能做到吗？
浏览 5提问于2010-07-31得票数 1
回答已采纳
我想在android的谷歌地图上绘制一条从源到目的地的路径。路径只是一条具有从源到目标的正向箭头的多段线。使用compute heading方法可以绘制...？
浏览 6提问于2017-04-19得票数 0
3回答
动态图中的最大流
、、
我正在寻找快速算法来计算动态图中的最大流量(添加/删除具有相关边的节点到图中)。也就是说，我们在G中有了最大流，现在添加/删除了带有相关边的新节点，我不喜欢重新计算新图的最大流，实际上，我想使用以前的结果来计算这个图。
任何不占用大量时间/内存的预处理都会被占用。另一个简单的想法是，保存之前的最大流量计算中使用的所有增加路径，现在为了添加顶点v，我们可以找到简单
浏览 0提问于2012-01-26得票数 10
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
