1回答
我想知道，如何计算一个带权重顶点的图的最短路径。像Dijkstra和Floyd-Warshall这样的经典算法通常适用于加权边，而我看不到如何将它们应用于我的情况(加权顶点)：我的一个想法是将图形转换为带有加权边的更经典的视图。这是我收到的：这里我们有单向和双向加权边，但我仍然不确定哪种算法会处理这一点，以便找到最
浏览 113提问于2018-12-04得票数 5
回答已采纳
4回答
寻找图中两点之间的最短路径是一个经典的算法问题，有许多好的答案(，等)。我的问题是，是否有一种有效的算法，在给定一个有向加权图、一对节点s和t以及一个值k的情况下，找到s和t之间的第k条最短路径。如果有多条相同长度的路径都与第k条最短路径相同，则算法可以返回
浏览 1提问于2011-08-27得票数 28
回答已采纳
我不是要求一个算法来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做)，而是在图包含至少一个从源顶点可以到达的负圈，并且从负圈可以到达目标顶点的情况下，是否存在多项式时间算法来寻找两点之间的最短路径
浏览 3提问于2013-09-02得票数 2
回答已采纳
1回答
我正在寻找一种路径查找算法，它不仅能给我最短的路径。我想用最少的步数得到最短的路径。 目前我正在使用Dijkstra's Algorithm来获得最短路径，但我并不坚持这样做。在我的例子中，你必须在某些有特定价格的地方停下来。所以我想要“最便宜”的路线，但我也想停下来的次数最少。
浏览 13提问于2019-10-16得票数 1
回答已采纳
1回答
我需要在带圈的加权图中找到两个节点之间最便宜和最短的路径。我正在Prolog中实现这一点。由于我必须找到最便宜的(最便宜的)和最短的(最短的)路径，所以我认为应该使用深度搜索来计算现有的所有可能的路径--首先使用回溯搜索，因为它的内存消耗较低，而且速度相对较快(我使用一个辅助列表来跟踪访问<e
浏览 7提问于2016-12-03得票数 2
回答已采纳
1回答
我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了
Dijkstra的算法22用于计算N个阶段的最短路径(步骤5)。考虑N= 2，在第一阶段，Dijkstra算法</
浏览 0提问于2015-11-25得票数 2
回答已采纳
1回答
我需要在s和t之间找到最短的O((V + E)*logV)路径。这将是一个非常简单的任务，如果我有一个经典的度量权重的路径。但事实并非如此。因此，经典的Dijkstra's algorithm with modified binary heap不起作用。我认为，我必须修改这个算法。我正试着去做，但我没有成功。Example.3与5之间的路径权
浏览 3提问于2014-12-20得票数 1
回答已采纳
1回答
BGP最佳路径选择算法
、、、、
，在列表中的13个中，最短AS_PATH是排序中的第4个算法。上面写着：重量:最高网络或聚合:本地起源原产地类型:最低原产地数
多出口鉴别器
浏览 0提问于2020-11-24得票数 1
回答已采纳
2回答
我正在尝试理解A*，统一成本和贪婪搜索算法是如何工作的。我知道探索节点的方式在所有三种算法中都会发生变化(贪婪将基于启发式值进行探索，A*基于启发式加距离，均匀基于距离)。我想知道，对于给定的源和目的地，是否所有3种算法都应该提供最短路径(只需探索不同数量的城市？)或者他们能提供一条不同的路径。我最困惑的是实现部分-如果你将节点存储在队列中，那么当你打算探索目标节
浏览 4提问于2016-10-04得票数 1
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i =
浏览 8提问于2021-02-22得票数 1
1回答
我已经检查过其他人的解决方案，但我不知道他们是如何解决这个问题的。
如果有人能帮我建议我应该从哪里开始学习来理解这些问题，那就太好了。
浏览 4提问于2016-06-20得票数 1
回答已采纳
2回答
我对量化投资领域非常陌生，但我想知道矩阵是否可以用来识别多货币兑换中的套利机会。这将是一种最短路径查找问题或用于不同其他问题集中的最小成本算法。
浏览 0提问于2012-07-04得票数 4
1回答
我正在尝试使用Python中的动态编程来计算最短路径。我将所有数据正确地存储为图的加权段(道路)和节点(城市)，所以这不是问题，因为我能够实现经典算法(BFS，DFS...)我只知道从A到B，我必须将问题分成子问题，但我不知道如何创建一个有效的算法，我的意思是算法应该遵循的步骤，以及我应该如何将问题分成小问题。
谢谢你的帮忙!
浏览 4提问于2018-11-28得票数 0
2回答
可多次访问顶点的TSP
、、、
我想解决一个问题，我有一个加权有向图，我必须从原点开始，至少访问所有顶点一次，并在最短的路径上返回原点。本质上，这将是TSP的一个典型例子，但i不有一个约束，即每个顶点只能访问一次。在我的例子中，任何不包括原点的顶点都可以沿着路径访问任意次数，如果这使得路径更短。例如，在包含顶点V1, V2, V3的图中，这样的路径是有效的，因为它是最短路径：
浏览 4提问于2016-10-03得票数 3
回答已采纳
1回答
设G=(E，V)是具有非负边代价的有向图.让我们做一个顶点。我需要找到一个算法，为找到每个顶点v，包含s和v的最短循环可能包含几次相同的边。最明显的解决办法是从s中运行Dijkstra，以求从s到每个v的最短路径，然后从每个v再运行Dijkstra，以求从v到s的最短路径，最短的循环是两者的结合。这是可行<em
浏览 2提问于2013-05-03得票数 2
回答已采纳
1回答
我感兴趣的是使用MATSim API计算基于链路权重的交通仿真路线。每个环节都有一个安全指标的属性，计算出的路径应该代表最安全的路径。Dijkstra路由算法计算最短路径。如果我能指定算法应该考虑安全指数而不是长度，那么使用它是非常完美的。我不知道在MATSim中是否可能做到这一点，也不知道是如何做到的。或者其他在MATSim中实现的路由算法可以
浏览 5提问于2016-06-07得票数 0
回答已采纳
1回答
一个人感兴趣的节点集合，让我们称之为这个集合S。
我们需要返回理想路径中最长的公共段中的最短部分。理想路径是在属于上述集合S的顶点上开始和终止的路径。不能保证公共路径的存在。我知道在线性时间内找到树中最长的路径，我们也可以很容易地将它扩展到理想路径的情况，但是经典的2 dfs算
浏览 1提问于2013-03-07得票数 1
1回答
Dijkstra的算法是f(n) = g(n)g( n )是从起始节点到n的路径的代价。h(n)是一个启发式函数，它估计从n到目标的最便宜路径的代价。为什么A*需要g(n)？
浏览 1提问于2018-09-20得票数 2
1回答
如果一个问题可以通过组合不重叠子问题的最优解来解决，这种策略称为“分而治之”。这就是为什么合并和快速排序不属于动态规划问题的原因。
是否有使用动态规划的应用实例？
浏览 1提问于2013-03-24得票数 16
回答已采纳
我知道，如果算法达到负循环，算法就不会终止，如果路径包含一个距离大于0的循环，那么它就不是最短路径。
我的问题是，如果存在一个循环距离为0的最短路径会发生什么，算法会将该循环包含在最短路径中吗？你会说所有的最短路径都是非循环的吗？
浏览 13提问于2017-06-20得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
云直播
腾讯会议活动推荐
腾讯云开发者
