1回答
给定一个布尔2D矩阵(基于0的索引)，查找是否存在从(0,0)到(x，y)的路径，如果存在一条路径，则打印到达它所需的最小步数，否则，如果目标不可达，则打印-1。你只能往上、下、左、右四个方向移动。每个测试用例的第一行包含表示矩阵大小的两个整数n和m。然后在下一行是矩阵的n*m个空格分隔值。它之后的下一行包含两个整数x和y，表示目标的索引。输出:对于每个测试用例，在新行中打印到达目
浏览 12提问于2020-05-23得票数 0
回答已采纳
2回答
全,考虑了加权邻接矩阵本身的乘法，但在这种情况下，我们用加法代替矩阵乘法运算，用极小化代替加法运算。注意，加权邻接矩阵本身的乘积返回一个矩阵，该矩阵包含任意一对节点之间长度为2的最短路径。
我的问题是，在一个图中，在一个路径<
浏览 7提问于2011-12-05得票数 3
回答已采纳
这是我应该贴出的完整标题，但它恰巧太长了：我画了一张图表，以使它更清楚。在左侧，"u“是源节点，"v”是目标节点。标记为1~6的节点为中间节点。从u -> v到曼哈顿的最短距离是12，但中间节点会形成堵墙。以u‘为源，v’为目的的右侧图表明，中间节点1到5不会阻塞从u‘到v’的最短</em
浏览 2提问于2012-01-08得票数 5
回答已采纳
1回答
在最短路径上
、、、
问题是找到从s1、...sk到t的最低合并成本，其中所有不同路径的访问顶点总数都是M (源和目标不计为已访问的顶点和0 <= M <= V=k+1，所以如果M=0时，所有路径都直接从源到目标)。，tk)和一个源，只需反转所有边缘并使源目标和目标源。我认为这可能是有用的，因为例如Dijkstra计算从一个源到<
浏览 0提问于2011-12-04得票数 0
3回答
我们得到一个加权图G和它的最短路径距离的矩阵Δ。因此，Δ(i，j)表示从i到j最短路径的权重(i和j是图的两个顶点)。初始给定的增量包含最短路径的值。突然，边E的权重从W减少到W‘。如何更新O(n^2)中的增量(i，j)？(图的顶点的n=number)问题不是再次计算具有最佳O(n^3)复杂度的所有对最短<em
浏览 2提问于2010-12-17得票数 4
1回答
问题是：
克里斯计划在一个有N个城市的国家旅行。他将从矩阵NxN得到帮助，该单元(I，J)表示从城市I到城市J的道路的长度。从城市A到城市B的道路的长度与从城市B到城市A的道路的长度不同。从相同的源城市返回的道路(直接)是0。克里斯注意到，从A到B的最短道路并不总是两个城市之间的直达道路。您需要帮助Chris找到最短路径
浏览 0提问于2020-01-11得票数 0
2回答
它具有单个源和一组目标(距离源最远的顶点)。我找到从源到每个目标的最短路径。其中一些路径是重叠的。我想要的是一个最短路径树，它最小化所有边的权重总和。
例如，考虑其中两个目标。假设所有边的权重相等，如果它们在大部分长度内共享一条最短路径，那么这比两条基本上不重叠的最短路径更可取(树中的边越少，总成本就越低)。另
浏览 2提问于2010-05-08得票数 7
1回答
书中说，重建最短路径树需要O(n+m)时间。但是，考虑到这些代码，我无法理解为什么它是O(n+m)而不是O(n*m) (因为我们有两个嵌套的for循环，一个嵌套在顶点上，另一个嵌套在传入边上)。书上说：
在这一部分中，我们证明了基于源s的最短路径树可以在O(n + m)时间内重建，给出了Dijkstra算法以s为源</
浏览 2提问于2022-07-03得票数 0
回答已采纳
1回答
得到的矩阵=一个矩阵，其中mati是以顶点I为源，顶点j为目标的最短路径。
我写了我自己的约翰逊算法的实现，我想知道它是如何处理负边的？最后，我所获得的距离矩阵与我运行弗洛伊德-沃尔时得到的距离矩阵不一样。这一点很明显，因为我们调整了图表的权重。这是否意味着Johnson的算法并不能帮助我们找到最短路径的代价，而只是哪条路径是最短的？另外，如果结果矩阵中<
浏览 3提问于2018-12-01得票数 0
回答已采纳
1回答
是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-
浏览 0提问于2015-11-25得票数 2
回答已采纳
1回答
我正在与一个科学的软件包一起工作，它大量使用igraph的最短路径算法来计算路径长度。然而，对于我们感兴趣的图表，返回的矩阵是非常内存密集型的，很容易扩展到10的Gb。我有两个问题：我在文
浏览 1提问于2020-10-14得票数 0
1回答
我试图通过计算所有对之间的最短路径，使用弗洛伊德-沃尔的算法在源和目标之间找到最短路径。我将第一个顶点存储在从i到j的最短路径上，当更新从i到j的最短路径时，它现在经过k，我将从i到j的最短路径上的第一个顶点设置为从i
浏览 3提问于2014-04-01得票数 3
回答已采纳
1回答
我有一个有N个顶点的完整图，我需要找到从给定源到给定目标的最短路径。所有边都有初始代价A，那么对于K边，代价将变为B。在顶点1和顶点N之间寻找最小代价的最佳方法是什么?算法在顶点1和顶点N之间找到最小代价(即最短路径)的方法是什么？输入是N，K，A，B和K边(成本为B的边)。其中：0 <= K <= 50
浏览 4提问于2014-04-16得票数 1
回答已采纳
我目前正在用Matlab编写最短路径算法。我写了它，这样我就可以计算出它的总成本。相反，我想做的是生成一个矩阵，这样我就可以存储最短路径中每个元素的当前成本的值。每当我试图改变我的值时，我总是得到错误，要么是矩阵越界了，要么是我的所有输出变量都没有定义。这是我的工作代码。我如何修改它，以便生成一个矩阵，该矩阵存储最短路径中所有元素的当前成本。下面的代码传入成本矩阵和维度的参数，并返
浏览 0提问于2015-02-26得票数 0
4回答
如果ArraN约束: a，则需要从(0,0)到(N1，N1)之间的矩阵，其中包含白色细胞、黑色细胞和一个灰色细胞。路径应该只覆盖白细胞，并且应该通过灰色单元格。访问过的节点不能再次访问。有些人建议进行搜索，但我不知道如何将其部署到这里。有人认为，首先要找到通往灰色细胞的最短路径，然后从灰色细胞中找到通往N-1，N1的最短路径。但我相信这在某些情况下行不通，因为灰色
浏览 10提问于2014-01-10得票数 3
回答已采纳
1回答
我尝试使用中的代码找到从单个源到n个顶点的最短路径 GraphGenerators.logNormalGraph(sc, numVerticesIterator.empty },)它给我提供了<
浏览 1提问于2017-08-09得票数 3
1回答
我要设计一个算法，运行在O(k(m + n))内，用于报告从s到t的k边最短路径。k边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，路径的总权重也必须是最小的。由于BFS不能单独使用来寻找最短路径(除非权重相等)，我认为运行时间意味着使用BFS来寻找具有k条边的
浏览 0提问于2013-03-14得票数 1
EA-B-C-DG OH PI QJ RK-L-M-N我必须找到从A节点到Q的最短路径。alt 21当我使用djikstra的算法时，主要的问题是我不能得到从源到目标的
浏览 18提问于2016-08-07得票数 1
云服务器
ICP备案
云直播
对象存储
腾讯会议
腾讯云开发者
