1回答
我目前正在尝试理解Yen的k条最短路径算法。我以原始论文和维基百科文章为基础，但仍然不明白为什么k> 2是正确的。事实上，我甚至不明白为什么它适用于以下例子：例如，让我们考虑从A到D的3条最短路径，即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该
浏览 0提问于2016-05-01得票数 2
回答已采纳
2回答
用A*算法求几条最短路径
、、、
我正在制作一个路由应用程序，它使用A*算法来查找路由。我想提供的不只是一条路线，还有几条替代路线。例如，仅比最佳路由稍长一点的路由。
由于A* (和其他许多)只找到一条路线，我如何搜索这些替代路线？我应该使用其他算法吗？
浏览 0提问于2015-02-26得票数 1
2回答
有n个顶点和m条边。所有边都有一个与之关联的权重。
我想设计一个算法，它将一个源顶点's'，一个宿顶点't‘和一个数字'k’作为输入。该算法的输出是从s到t的最短路径，其中k个顶点位于s和t之间。
浏览 1提问于2013-03-30得票数 2
因此，dijkstra算法是搜索加权(无负)连通图最短路径的最佳算法。Dijkstra算法可用于寻找两点/顶点的最短路径。它可以用来寻找所有顶点的最短路径。
问题:我的理解正确吗？它也能用来寻找某些顶点的最短路径吗？例如，图有A，B，C，D，E，F，G，H，I，J，K，我们只对A，B
浏览 2提问于2018-03-12得票数 1
4回答
寻找图中两点之间的最短路径是一个经典的算法问题，有许多好的答案(，等)。我的问题是，是否有一种有效的算法，在给定一个有向加权图、一对节点s和t以及一个值k的情况下，找到s和t之间的第k条最短路径。如果有多条相同长度的路径都与第k条最
浏览 1提问于2011-08-27得票数 28
回答已采纳
1回答
有没有人知道我如何编写一个编程的图算法(C++代码会很棒)，它可以为循环图中给定的一组节点和边找到第k条最短路径？例如，最短路径(可以由Dijkstra或Bellman Ford找到)被认为是第1个最短路径。现在第二个最短路径是位于第一个最短路径之后的最短路径。现在我想让<e
浏览 0提问于2012-02-20得票数 1
回答已采纳
1回答
有没有什么方法可以用多项式的复杂度(或者更好)得到一个无向图的第k条或k条最短路径？ 或者，Yen的k最短路径算法可以修改为无向图吗？
浏览 21提问于2018-12-31得票数 0
1回答
最长最短路径(不完全)
、、、
在我的学士论文中，我遇到了以下问题(解决可能对论文的实际问题有用的问题)。我有一个带有顶点V和来自V的两个顶点的加权有向图G，起始t和目的地t。我最多只能移除k顶点。我需要找到顶点，在调整后的图中，删除顶点将最大化从s到t的最短路径的成本(长度)。
我想，这个问题以前应该在文献中得到解决，但是我没有找到相关的文章。如果有任何相关文献的链接，我将不胜感激。
浏览 1提问于2017-02-28得票数 3
4回答
使用下面的代码，我试图找到第二条最短路径/第k条最短路径. public static void shortestPathEdgeModel(2, 4, 8), new EdgeModel(4, 1, 20)
从0到4
浏览 0提问于2019-07-17得票数 1
我想找一个图中2个顶点之间的下一条最短路径，并且这条路径有一个正的cost.The，下一条最短路径是允许共享边的最短路径，我可以使用.Which算法吗？
浏览 0提问于2011-02-12得票数 20
回答已采纳
众所周知，A星算法是完全的。然而，我发现搜索web的所有实现似乎只返回第一个(最佳)解决方案。例如，这个实现：
由于算法总是以最小f值扩展节点，而且当第一个节点是解决方案时，实现似乎停止了，那么如何调整上述代码，从而输出所有(或第一个n)导致目标的路径，而不考虑重复的操作(即一次又一次包含相同操作的路径
浏览 2提问于2013-01-30得票数 1
1回答
我是OrientDB的新手，我正在尝试在我的graph.So中找到前k个最短路径我正在应用Yen的算法创建我的算法，但我不知道如何在OrientDB中使用它，或者是否有其他方法可以在东方图中找到K-最短路径感谢所有人的帮助:]
浏览 1提问于2016-01-19得票数 0
我试图确切地理解这些算法是如何工作的，但我一直无法找到一个简单的解释。如果有人能提供或给我一个比原始论文中的描述更容易理解的这些算法的描述，我将非常感激。谢谢。
浏览 0提问于2012-10-13得票数 11
在一个有向图中(假设它有很多圈)，我需要计算每个节点的特定节点可以到达的节点数。我如何才能以最小的努力做到这一点？我需要使用哪种算法？注意:我认为这个问题的一个合理的算法应该递归地计算这个数字(就像'node a‘的结果取决于'node b’的结果，如果a连接到b)。
浏览 0提问于2011-12-18得票数 3
回答已采纳
在弗洛伊德-沃肖尔算法中，为任何一对顶点计算最短路径成本。额外的记账使我们能够将实际路径(顶点列表)保持在最短路径上。我如何扩展Floyd-Warshall，以便对任何一对顶点，都能找到top-K最短路径？例如，对于K=3，结果将是计算并维护3条最短路径？
我一直在使用来自Sedgewick的。
浏览 6提问于2014-08-23得票数 0
1回答
用图工具求k条最短路径
、、、
我有一个有向图，我试图找出最上面的k条最短路径。目前，我已经在图形工具中实现了网络，它提供了一个最短路径算法，但根据我所能知道的，没有k个最短路径算法。我遇到过这个帖子()，但我毕竟不是连接两个节点的路径。
似乎NetworkX有一个用于此()的函数。是否有办法在图形工具中这样做，还是我更好地切换工具箱和使用NetworkX？
浏览 2提问于2016-02-23得票数 1
回答已采纳
在最大二部匹配的Hopcroft-Karp算法中，为什么我们总是在广度优先搜索中寻找最短的增广路径？是不是因为广度优先搜索总是找到最短的路径？我只是搞不懂为什么增强路径是最短的，这很重要。
浏览 2提问于2013-05-15得票数 0
回答已采纳
我刚刚开始学习图的算法，更具体地说-- Floyd-Warshall算法。在中查看修改后的允许路径重建的算法，我注意到它保留了中间节点，而不是更符合逻辑的方式(在我看来)-保存下一跳。为什么要以这种方式保存路径？
浏览 0提问于2013-11-08得票数 0
3回答
全对最短路径，领带断裂
、、、
我正在创建一个程序，它将计算未加权图中所有节点的Betwenness中心性。要做到这一点，我必须找到ASSSP (所有单一源最短路径)。在创建程序时，我意识到最终我将有联系(从源到目的地的距离相同，但路径不同)。这使我想到了这个问题。我该如何解决这些关系？如果我使用随机的断线器，那么对于相同的输入，中间中心度的每个输出可能略有不同。可见，有两条路径(A->B->D和A->C->D)，bot<e
浏览 2提问于2012-07-11得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
