腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
求解特定情况下替换
路径
问题的
算法
algorithm
、
graph-theory
、
graph-algorithm
、
shortest-path
(A)假设给出了一个边加权有向图G,其中从顶点s到顶点t的
最短
路径
σ通过G的每个顶点,
描述
了计算G中从s到t的
最短
路径
距离的
算法
,对于G的每一个边e,在O(VlogV)时间内计算
最短
路径
距离。您的
算法
应该输出一组E
最短
路径
距离,一个对应于输入图的每个边。您可能假设所有的边权都是非负的。[提示:如果删除原始
最短
路径
的边缘,新旧
最短
路径</e
浏览 8
提问于2019-12-20
得票数 0
2
回答
找出图中所有顶点之间的
最短
路径
,而不给出起点或终点
matlab
、
graph
、
artificial-intelligence
、
shortest-path
我知道旅行推销员问题,但有没有其他
算法
/问题更适合我的需求/
描述
?我需要借助这样的数学
描述
来
描述
我的问题。 我有一组节点,它们的起点和终点都是已知的。所以我只需要计算访问这两个点之间的所有三个点的
最短
方式。Dijkstra和类似的
算法
试图找到两点之间的
最短
路径
,所以在这里他们可能不会访问两点之间的所有点。或者有没有一个
算法
可以找到
最短
路径
并访问两点之间的所有点?
浏览 0
提问于2013-10-23
得票数 2
1
回答
A和B之间的路线
algorithm
、
graph-theory
、
shortest-path
、
traveling-salesman
我知道旅行推销员的问题,但是还有其他更适合我的需要/
描述
的
算法
/问题吗?我需要用这样的数学
描述
来
描述
我的问题。 对于已知的起始点和端点,我最多有五个点。因此,我只需要计算出
最短
的方式,去访问这两者之间的所有三个点。Dijkstra和类似的
算法
试图找到两点之间的
最短
路径
,所以在这里他们可能不会访问两个点之间的所有点。还是有一种
算法
能找到
最短
的
路径
并访问两点之间的所有点?
浏览 0
提问于2013-09-24
得票数 1
回答已采纳
3
回答
是Bellman“所有对”还是“来自一个节点”
最短
路径
的结果?/是否有一个全对Bellman版本?
algorithm
、
graph
、
bellman-ford
我最近正在学习图形
算法
,在我的大学里,我们被教导说,Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对
最短
路径
)。然而,我不明白这个
算法
是如何实现的,我试图通过观看YouTube视频和查找维基百科中的定义来理解它……我无法找到
描述
该
算法
的资源,其结果将是所有对
最短
路径
表,但只能“从一个节点到所有其他节点对Bellman
算法
进行调整以实现所有对
最短
路径
表,还是我的大学
浏览 8
提问于2017-07-16
得票数 1
回答已采纳
2
回答
用A*
算法
求几条
最短
路径
algorithm
、
graph
、
routing
、
shortest-path
我正在制作一个路由应用程序,它使用A*
算法
来查找路由。我想提供的不只是一条路线,还有几条替代路线。例如,仅比最佳路由稍长一点的路由。 由于A* (和其他许多)只找到一条路线,我如何搜索这些替代路线?我应该使用其他
算法
吗?
浏览 0
提问于2015-02-26
得票数 1
1
回答
具有最小费用下界约束的单源
最短
路径
algorithm
、
graph-algorithm
问题
描述
:我知道有了这个限制,像Bellman ford这样的传统SSSP
算法
不能正常工作。我该如何为这个问题找到最有效的
算法
呢?
浏览 1
提问于2017-10-25
得票数 2
1
回答
在线性时间内从顶点找到最轻的
路径
algorithm
、
graph
、
computer-science
众所周知,对于每个 u都有一条最轻的
路径
(按权重计算),这也是从r到u的
最短
路径
(按边缘)。
描述
一种从r到每个u查找最轻
路径
的
算法
。所以我想的就是简单地从r运行一个BFS
算法
,只需做一个简单的更改;当我们到达一个顶点v时,我们对从它出来的所有边进行排序,并按照边的顺序(从最小到最大)排列顶点。这样我们就可以得到一个
最短
路径
图( BFS应该这样做),但我们也喜欢两个
最短
路径
中最轻的
路径</em
浏览 1
提问于2016-09-14
得票数 1
回答已采纳
1
回答
决定是否所有从s到t的
最短
路径
都包含边e
graph-algorithm
、
dijkstra
、
shortest-path
、
bellman-ford
设s,t是V中的2个顶点,E是e中的一条边,
描述
一个
算法
,该
算法
决定从s到t的所有
最短
路径
是否都包含边e。这就是实现Dijsktra时间复杂度的方法:只需从s运行Dijkstra并计算增量(s,t) (从s到t的
最短
路径
的权重)。删除边e,并从新图中的s再次运行Djikstra。如果新图中的增量(s,t)增加了,这意味着从s到t的所有
最短
路径
都包含边e,否则就不是真的。 我想知道是否有更有效的
算法
来解决这个问题。你认
浏览 6
提问于2013-03-04
得票数 0
回答已采纳
2
回答
有向图所有路的最小权边
algorithm
、
directed-graph
给定一个边权为-ve或+ve的有向图,找到从顶点s到顶点d的所有
路径
的最小权边的
算法
是什么?
浏览 0
提问于2017-11-13
得票数 0
1
回答
改进的
最短
路径
算法
,禁止
路径
graph
、
dijkstra
、
shortest-path
我们被要求找到从A到B的
最短
路径
,只要我们遵循以下条件:从1到4的
路径
是1 -> 4,1 -> 2 -> 3 -> 4,1 -> 3 -> 4。其中,只有1~2条为有效<e
浏览 0
提问于2016-09-22
得票数 2
回答已采纳
1
回答
计算N条
最短
路径
的Dijkstra
算法
algorithm
、
networking
、
routing
、
dijkstra
、
shortest-path
我知道Dijkstra从一个源输出到图中所有节点的
最短
路径
,但当我正在读一篇研究论文时,作者提到了使用Dijkstra计算s和t之间的N条
最短
路径
,这让我有点困惑。以下引用原文:利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了 Dijkstra的
算法
22用于计算N个阶段的
最短
路径
(步骤5)。考虑N= 2,在第一阶段,Dijkstra
算法
确定了两个网络设备之间
最短
的路由,从而使所有链路开销的权重增加了10倍。紧接着,在第
浏览 0
提问于2015-11-25
得票数 2
回答已采纳
4
回答
图中从单个源到单个目的地的
最短
路径
algorithm
、
shortest-path
从上我了解到了一些根据给定条件计算
最短
路径
的
算法
。最著名的
算法
之一是Dijkstra's algorithm
算法
,它寻找从源顶点到图中所有其他顶点的
最短
路径
。但是通过使用Dijkstra's algorithm,我不需要探索所有的顶点,然而我的目标只是找到从单个源到单个目的地的
最短
路径
。我应该在这里使用哪种策略?这样我就不需要探索所有其他的顶点了。当我第一次在两个树中找到任何相同的child时,我可以同时停止bfs
浏览 0
提问于2012-04-07
得票数 2
回答已采纳
1
回答
Bellman
算法
和步骤数
algorithm
、
graph
、
tree
、
shortest-path
、
bellman-ford
我们希望用Bellman-Ford
算法
来寻找顶点1 (V_1)到其他顶点之间的
最短
路径
。这种
算法
在每一步中都会以任意的顺序检查所有的边缘。如果在一个步骤中,V_1到所有其他顶点的
最短
路径
(从以前的值),则该
算法
将停止!在这个
算法
中,最大和最小的步骤是多少? 有人能
描述
我为什么选择(2)来回答这个问题吗?
浏览 2
提问于2015-03-03
得票数 2
1
回答
使用限制提升c++ Astar
c++
、
boost
、
graph
、
grammar
、
a-star
我使用的是boost 的astar
算法
我想为从起始节点到目标节点的
路径
长度积分一个长度条件。更具体地说,我试图找到一个精确长度为11位的数字链。更一般的是,我正在寻找一种方法,将语法检查集成到A*
算法
中。在我的具体例子中,语法可以用一个规则模式来表示,比如^1-9\d{10}$每个节点代表一个字符(这里是一个数字)。任何建议都是值得感谢的。
浏览 2
提问于2017-12-27
得票数 0
1
回答
Dijkstra
算法
:所有
最短
路径
都是非循环的吗?
shortest-path
、
dijkstra
我知道,如果
算法
达到负循环,
算法
就不会终止,如果
路径
包含一个距离大于0的循环,那么它就不是
最短
路径
。 我的问题是,如果存在一个循环距离为0的
最短
路径
会发生什么,
算法
会将该循环包含在
最短
路径
中吗?你会说所有的
最短
路径
都是非循环的吗?
浏览 13
提问于2017-06-20
得票数 0
6
回答
通过加减两个整数之间的
最短
路径
algorithm
、
math
、
numbers
、
theory
、
equation
下面是对这个问题的
描述
: -5 + 12 + 12 = 191 + 7 - 5 = 2谢谢!
浏览 5
提问于2011-09-02
得票数 17
回答已采纳
1
回答
我混淆了
最短
路径
查找
算法
和图遍历
算法
。
algorithm
、
graph-theory
、
depth-first-search
、
shortest-path
、
path-finding
我的理解是,BFS和DFS是图遍历
算法
,而其他
算法
(如A*和dijkstra )则用于在图的两个节点之间寻找
最短
路径
。但是在一些地方,我认为BFS和DFS也被称为
最短
路径
查找
算法
。请详细说明图遍历
算法
与
最短
路径
查找
算法
的区别。谢谢!
浏览 6
提问于2022-05-06
得票数 0
1
回答
Yen的k
最短
路径
算法
algorithms
、
graph
、
path-finding
我目前正在尝试理解Yen的k条
最短
路径
算法
。我以原始论文和维基百科文章为基础,但仍然不明白为什么k> 2是正确的。事实上,我甚至不明白为什么它适用于以下例子:例如,让我们考虑从A到D的3条
最短
路径
,即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该
算法
的了解,正确地计算了2条
最短
路径
。然而,第三条
最短
浏览 0
提问于2016-05-01
得票数 2
回答已采纳
2
回答
隐图上令人惊叹的
算法
族
algorithm
、
complexity-theory
、
graph-theory
、
dynamic-programming
根据定义,动态编程几乎是在隐式dag上找到
最短
/最长
路径
。每个DP
算法
都是这样做的。 可以松散地
描述
为在隐式平面图中计算完美匹配的东西。所以,我的问题是:有没有其他的
算法
家族在隐式图上使用众所周知的
算法
来实现相当大的加速比?
浏览 0
提问于2010-04-22
得票数 3
回答已采纳
1
回答
在删除后选择要重新插入的最佳边缘的
算法
algorithm
、
graph-theory
、
graph-algorithm
、
bellman-ford
假设我们想要重新插入从G回到H的一条边,这样得到的图中从s到t的
最短
路径
是尽可能短的。
描述
和分析一个
算法
,以选择最佳的边缘重新插入。我认为它需要与bellman
算法
一起用于我们删除的每一个边,然后从所有的边中找到
最短
的
路径
。但是它的运行时间太长了。有人有更好的主意吗?谢谢:)
浏览 2
提问于2016-01-12
得票数 1
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券