腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
具有
顶点
遍历
顺序
约束
的
从
源
到
目的地
的
最短
路径
graph
、
graph-algorithm
、
shortest-path
、
breadth-first-search
假设我们有一个
具有
V个
顶点
和E个边
的
双向图,其中所有边
的
权重都是1。现在,除
源
之外
的
每个
顶点
都有自己
的
级别,并假设我们想要达到级别L。假设我们
从
级别1开始。当级别是i时,我们只能通过级别0或级别i
的
顶点
。在通过一个
具有
级别i
的
顶点
后,我们将级别提升1。 现在,给定起点和目标水平,我们如何计算达到目标水平所需
的
最小步骤(成本)?我
浏览 6
提问于2019-06-13
得票数 2
1
回答
高效
的
Dijkstra用于多种来源和多个目标
algorithm
、
graph
、
dijkstra
我正在寻找一种有效
的
方法来
遍历
一个包含多个
源
顶点
和多个目标
顶点
的
大图。具体来说,如果存在这样
的
路径
,我希望为每个(
源
、目标)对找到
最短
路径
。显然,这可以通过对每个源点
的
宽度优先搜索来完成,但是考虑
到
图中
的
许多
路径
将被多次
遍历
,我想会有一个更短
的
方法。图是有向
的
浏览 2
提问于2019-10-07
得票数 2
2
回答
广度优先搜索如何找到
从
源
顶点
到目的
顶点
的
最短
路径
?
algorithm
、
graph-theory
、
breadth-first-search
有人告诉我,BFS可以为您提供
从
源
顶点
到目标
顶点
的
最短
路径
,这是有意义
的
,因为您
遍历
相邻节点。然而,我看不到如何保证总是会发生这种情况。在BFS伪代码逻辑中,我看不到选择正确
的
相邻节点来保证
具有
最短
路径
。BFS可以随机选取任何相邻节点,最终得到
从
源
顶点
到目标
顶点
的
更长
浏览 1
提问于2020-11-30
得票数 1
1
回答
在有向图中,
最短
路径
s-t总是包含图
的
最小边吗?
algorithm
、
graph-theory
关于下列问题: 考虑有向图
具有
不同
的
非负边长和一个
源
顶点
,修正了一个目标
顶点
t,并假定该图至少包含一条s
路径
。下列哪一种说法是正确
的
?
最短
的
s-t路必须排除G. vertices.The -t
路径
的
最大长度边有一条没有重复
顶点
的
最短
s-t
路径
(即“简单
的
”或“无刷
的
”这样
的
<
浏览 9
提问于2022-08-14
得票数 0
回答已采纳
1
回答
具有
最小费用下界
约束
的
单
源
最短
路径
algorithm
、
graph-algorithm
问题描述: 给定adjacencyMatrix和adjacencyList中
的
一个图G,其中有一个
源
顶点
s和一个目的
顶点
d。找出
从
s
到
d
的
带
约束
的
最短
路径
。
约束
是
最短
路径
成本c
具有
下界,即成本c必须大于分配
的
下界N,但在大于或等于N
的
所有可能
路径
的
成本中是最
浏览 1
提问于2017-10-25
得票数 2
2
回答
如何利用Dijkstra算法寻找
具有
顶点
约束
的
最短
路径
algorithm
、
graph
、
dijkstra
基本上问题是这样
的
:给定一个无向简单加权连通图,在访问给定集合
的
至少一个
顶点
时,我们必须找到
从
给定
源
到
给定
目的地
的
最短
步行,同时访问集合B中
的
至少一个
顶点
,附加
的
约束
条件是,集合B
的
顶点
应该总是在访问集合A
的
顶点
之后才能到达,而且图中可能存在既不属于A也不属于B
的
顶点
浏览 2
提问于2020-06-07
得票数 1
回答已采纳
4
回答
图中
从
单个
源
到
单个
目的地
的
最短
路径
algorithm
、
shortest-path
我
的
图不包含将
顶点
连接到自身
的
边。两个
顶点
之间只有一条边。从上我了解到了一些根据给定条件计算
最短
路径
的
算法。最著名
的
算法之一是Dijkstra's algorithm算法,它寻找
从
源
顶点
到图中所有其他
顶点
的
最短
路径
。但是通过使用Dijkstra's algorithm,我不需要探索所有的
顶点
浏览 0
提问于2012-04-07
得票数 2
回答已采纳
2
回答
最短
路径
不是图中
的
路径
algorithm
、
graph
、
shortest-path
我想知道是否有一种算法可以在图中找到
最短
路径
。 假设我有一个图,从一个
顶点
到另一个
顶点
有一对
路径
。这些
路径
中
的
两条或更多条
具有
相同
的
成本。如何标记、查找这些
顶点
之间
的
所有
最短
路径
?据我所知,Dijkstra或Bellman-Ford算法会找到
最短
路径
,但他们只“选择”一条。
浏览 1
提问于2010-08-09
得票数 1
回答已采纳
1
回答
使用pregel graphx实现一对一
最短
路径
scala
、
apache-spark
、
shortest-path
、
spark-graphx
我尝试使用中
的
代码找到
从
单个
源
到
n个
顶点
的
最短
路径
GraphGenerators.logNormalGraph(sc, numVerticesIterator.empty },)它给我提供了<
浏览 1
提问于2017-08-09
得票数 3
5
回答
使用Dijkstras找到"k“
最短
路径
c#
、
algorithm
、
dijkstra
、
path-finding
我已经可以使用Dijkstra
的
算法:找到两个
顶点
之间
的
最短
路径
。是否有可能在第一条路线上
遍历
所有的前辈,然后从前身运行Dijkstras
到
目的地
(并且不包括先前
的
下一个
顶点
的
原始选择)。这样我就能找到所有可能
的
路线,然后互相比较? 举例说明。A=
源
浏览 10
提问于2014-06-15
得票数 3
回答已采纳
1
回答
如何在访问至少一个有向图
的
目标时,找到
从
顶点
u
到
v
的
最短
路径
?
algorithm
、
graph-theory
、
shortest-path
我很难在最坏
的
情况下(E是边
的
列表,而V是图中
的
顶点
),在最坏
的
情况下执行这一任务。 到目前为止,我尝试使用邻接列表。我首先用Kahn
的
拓扑算法
从
顶点
u开始对图进行排序。然后在排序
的
拓扑中查找下一个目标,并在
遍历
目标时将从
顶点
u
到
v
的
最小距离推到最小堆中。我用Dijkstra算法找到了
从
u
到
需要最小总距离
的
目标
浏览 1
提问于2022-04-12
得票数 2
1
回答
广度优先搜索计数器示例
graph-theory
声明:我知道,当涉及
到
从
BFS派生
的
最短
路径
树时,
浏览 5
提问于2018-11-20
得票数 0
1
回答
O(log )中
的
广度优先搜索
c++
、
c
、
algorithm
、
graph
在一个有循环和负边
的
无向图中,使用BFS (使用
遍历
的
最小
顶点
)在O(log )时间内找到
目的地
是可能
的
吗?很明显,图G只包含一个圈,您可以假设这个圈
的
长度是奇数(这个圈中有奇数个
顶点
)。
顶点
的
编号
从
1
到
N。每条边都被指定了相应
的
整数权重。您
的
任务是刺激两种类型
的
查询:更新由f u v表示
的
查询:将
最短
浏览 0
提问于2013-05-11
得票数 2
3
回答
在经过特定
顶点
的
有向图中最轻量级
的
圆圈
algorithm
、
graph-algorithm
、
weighted-graph
有向图G(V,E)有权函数w,所以每个(u,v)
的
权都是正值。我需要找到图中最轻量级
的
圆,
顶点
k‘是其中
的
一部分。我还给出了一个我可以使用
的
算法,它可以为
具有
正权值
的
图找到最轻量级
的
路径
(我只能使用它一次)。 我考虑创建一个子图G‘,其中所有的
顶点
和边都是强连通
的
分量。找出k‘是其中一部分
的
图。然后找出
从
k‘
到
某些
顶点
v
浏览 3
提问于2017-11-21
得票数 0
回答已采纳
3
回答
在没有给定边
的
情况下
的
最短
路径
algorithm
、
shortest-path
该图包含N个
顶点
(编号
从
0
到
N1)和M个双向边。在任意两个
顶点
之间最多有一条边,也没有自循环(ie.no边将
顶点
连接到自身)。给出了
源
顶点
的
S和目标
顶点
D。 设Q为查询数,每个查询包含一个边e(x,y)。对于每个查询,我们必须找到
从
源
S
到
目的地
D
的</e
浏览 5
提问于2012-06-05
得票数 10
回答已采纳
2
回答
有没有真正
的
单对
最短
路径
算法?
algorithm
、
shortest-path
今天我遇到了这个词“单对
最短
路径
问题”。我想知道对加权图是否存在单对
最短
路径
算法。我
的
推理可能有缺陷,但我想,如果你想找到A和Z之间
的
最短
路径
,你绝对必须知道
从
A
到
B,C,D,……
的
最短
路径
。Y.如果你不知道后者,你就无法确定你
的
道路实际上是
最短
的
。因此,对于我来说,任何
最短
路径</e
浏览 4
提问于2017-03-30
得票数 10
回答已采纳
2
回答
带另一
约束
的
最短
路径
algorithm
、
graph-algorithm
、
shortest-path
给定一个加权无向图,需要找到两个节点之间
的
最短
路径
,这实际上是一个经典
的
最短
路径
问题。但是还有一个
约束
:每个节点都包含一个“约简”值,可以用来降低一个
遍历
的
下列边
的
成本(不仅是相邻
的
,而且约简也不是累积
的
)。因此,您可以使用您之前所经历过
的
一个节点中
的
“约简”来降低边缘
的
成本(每个边
的
最终成本不能小于0)。让我
浏览 0
提问于2018-02-17
得票数 2
回答已采纳
1
回答
源
顶点
和目标
顶点
之间
的
最短
路径
(all)
algorithm
、
graph
给出
具有
边权
的
无向图(G)。如何找到
从
源
到
目的地
的
所有可能
的
最短
路径
。我不能修改Dijkstra
的
algo,但允许通过提供输入将其作为一个过程使用。我
的
第一种方法是运行Dijkstra;提取第一组
最短
路径
,然后
从
图中提取这些边,然后再运行Dijkstra。我们运行它,直到
从
源
到</em
浏览 1
提问于2022-09-28
得票数 0
1
回答
两点间
最短
路径
的
算法
algorithm
、
floyd-warshall
我有一个
具有
所有正权重
的
加权图。我需要找到
从
顶点
x到
顶点
y
的
最短
路径
。在这种情况下,我是否应该更喜欢Floyd-Warshall算法而不是Dijkstra
的
算法,因为我对
从
单个
源
到
所有
顶点
的
最短
路径
不感兴趣,而只是对特定
的
2个
顶点
之间
的
最短
浏览 3
提问于2019-11-19
得票数 1
2
回答
逆图上
的
Dijkstra算法
algorithm
、
data-structures
、
graph-theory
、
dijkstra
如果我们将图G反转到G‘,并从
源
顶点
't’对G‘运行Dijkstra算法,这个算法会给出
从
所有
顶点
到G中't’
的
最短
路径
吗?有人能证明或找到反例吗?
浏览 6
提问于2018-11-02
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
第二次:深度&广度优先算法
Python一文简单看懂 深度&广度 优先算法
10种常用的图算法直观可视化解释
到底什么是路由?
掌握机器学习数学基础之信息论及其他(三)
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券