-
0 votesanswersviews
邻接矩阵中的寻路
给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历一个点并返回它需要多少次移动？ Example 鉴于此数组 int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } }; 我像这样制作一个相邻的矩阵...... 0 1 2 3 4 0 [0] [1] [1] [0] [... -
0 votesanswersviews
使用邻接矩阵在迷宫图中找到最短路径
我在解决一个特定问题时遇到了一些麻烦，即在迷宫图中找到最短路径 . 可能是因为迷宫是由像_2458686这样的四维数组初始化的事实而陷入困境 . 第一对和第二对索引在行/列形成中指定图中的位置 . 该图如下所示： XXXXXXXXXXXXX ..........X.X X.XXX.XXX.X.X X.X.X...X.X.X X.X.XXX.XXX.X X...X.....X.. XXXXXXXXX... -
0 votesanswersviews
如果我们有能力克服MOST 1障碍，那么计算从开始到结束的最短路径
我们以2D整数矩阵的形式给出了一个迷宫;其中0是可通空间，1是墙 . 起始位置始终是： array[0][0] 并且结尾将始终为： array[HEIGHT -1][WIDTH-1] 唯一可能的移动是向上，向下，向右或向左 . 我想找到从开始到结束的最短路径，考虑到我们最多可以克服迷宫内的一面墙 . 我开始创建一个Maze类和一个Vertex类 . 我的第一个想法是使用BFS，但是，我最近意识... -
31 votesanswersviews
如何计算网格中两点之间的最短路径
我知道有很多算法可用于计算图形或网格中两点之间的最短路径，如广度优先，全对（Floyd's），Dijkstra's . 但是，正如我所注意到的，所有这些算法都计算出该图或网格中的所有路径，而不仅仅是我们感兴趣的两点之间的路径 . 我的问题是：如果我有一个网格，即一个二维数组，我有兴趣计算两点之间的最短路径，比如P1和P2，如果我可以在网格上移动的方式有限制（例如，只对角，或只对角和向上等），什么算... -
12 votesanswersviews
最小生成树和最短路径树是否始终共享至少一条边？
我正在研究图论，我对最小生成树和最短路径树之间的联系有疑问 . 设 G 是一个无向连通图，其中所有边都加权 with different costs . 设 T 为 G 的MST，让 T 为某个节点 s 的最短路径树 . 是否 T 和 T 保证分享至少一个优势？ 我相信这并非总是如此，但我找不到反例 . 有没有人有关于如何找到反例的建议？ -
1 votesanswersviews
Bellman Ford算法无法计算有向边加权图的最短路径
当我在书Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne中遇到下面的问题时，我最近了解了最短路径算法 . 假设我们将EdgeWeightedGraph转换为Directed EdgeWeightedGraph，方法是在EdgeWeightedGraph中为每个Edge创建EdgeWeightedDigraph中的两个Directe... -
1 votesanswersviews
neo4j cypher如何在关系中找到特定节点的存在计数？
在我的应用程序中，我将尝试计算节点的中介中心性 . 这是Betweenness Centrality Calculation Formula . Deminator只是两个节点之间关系的计数 . 但是，分子是这种关系之间特定节点的存在计数 . 那么如何才能找到关系中节点的存在计数？ 例如，由于这个密码： MATCH p=allShortestPaths( (u1{name:1174}) - [*... -
1 votesanswersviews
寻找迷宫中最短路径的地雷和有限的生命
我遇到了一个问题，我在解决方面遇到了一些麻烦 . 我正在尝试编写一个程序来解决一个m网格迷宫，其中有地雷 . 棘手的部分是玩家/迷宫跑者的生命数L> = 1，这意味着他们可以踩下最多的L - 1地雷，然后才能在下一枚地雷上死亡 . 更多详情： 每个单元可以连接到任何相邻单元 . 所有连接都是双向的 . 我们可以假设迷宫在给定生命数量的情况下从开始到结束都有正确的路径 . 迷宫... -
1 votesanswersviews
Dijkstra的拓扑排序算法
我在教科书中看到了这段经文： “如果图形是非循环的，我们可以改进Dijkstra算法 . 顶点可以按拓扑顺序选择，因为当选择顶点时，它的距离不能再降低，因为没有来自未知节点的入射边缘 . ” 我理解拓扑排序和Dijkstra的算法，但不理解拓扑顺序如何帮助加速Dijkstra，特别是当订单并不总是唯一时 . （除非它指的是没有意义的空间复杂性） 有人能解释一下如何改进它并举个例子吗？ -
1 votesanswersviews
巨型图中的最短路径
现在我研究的图表通常不适合任何类型的内存或存储设备 . 我的问题是我需要在这些图中找到两个特定顶点之间的最短路径 . 我知道C的boost图库，我很开心 . 使用boost的图形库（以及其他图形库）的常用概念就是这样 在内存中创建顶点列表 在内存中创建边缘连接列表 调用您想要的图算法 这种方法适用于适合RAM的图形： typedef adjacency_list< v... -
3 votesanswersviews
将循环图分解为最小数量的最短路径子图
给定一个循环图，我正在寻找一种算法，将该图分解为非循环子图 . 这些子图中的每一个都具有根顶点，其中该顶点是计算最短路径的源 . 例如，给定下面的循环图，其中循环在3,4和5之间： +-------------------------+ | | | ... -
0 votesanswersviews
凯文培根游戏的最短路径图遍历
我一直在尝试为流行的凯文培根游戏创建一个图形表示 . 我已经创建了图形和顶点类，但是在创建宽度第一搜索方法来遍历图形并找到从凯文培根到演员的最短路径时遇到了一些麻烦，并在路上打印出边缘 . 用户应该输入一个演员，程序应该找到从凯文培根到该演员的最短路径 . 然后用户将继续进入演员，并且将获取到该演员的最短路径，并打印出凯文培根数字，否则它将打印出来 . 有一个顶点和图表类 . 顶点类是一个字典，它... -
15 votesanswersviews
有效地找到大图中的最短路径
我正在寻找一种方法来实时找到巨大图形中节点之间的最短路径 . 它有数十万个顶点和数百万个边 . 我知道之前已经问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道可以用什么软件来实现它 . 例如，如果已经存在用于在无向图中执行bfs的库（使用python绑定！），那将是完全完美的 . -
0 votesanswersviews
线性时间单对最短路径算法？
是否有一种算法可以解决 linear time 中的单对最短路问题（即有向和无向边或无向边表示为两个有向边）， negative, real edge-weights 和 non-negative cycles ？ Wikipedia仅提及问题的单源和全对变体的算法 . 我知道解决其中一个问题的这些问题也解决了单对问题，但是它们都没有在线性时间和所有上述标准中起作用 . 因此，对于具有上述所有标准... -
2 votesanswersviews
网格中的最短路径
我有一个二维矩阵 A......... ##....##.. .####...## .......... .......### B......... ####...### #...#.###. 其中' . ' represents path and ' # '代表墙 . 我必须找到从点 A 到点 B 的最短路径 . 我熟悉 BFS 算法，它似乎是一个合理的算法 . 但是我觉得在网格上应用... -
7 votesanswersviews
如何最小化最短路径树的总成本
我有一个带有正边权的有向无环图 . 它有一个源和一组目标（距离源最远的顶点） . 我找到了从源到每个目标的最短路径 . 其中一些路径重叠 . 我想要的是一个最短路径树，它最小化所有边缘的权重总和 . 例如，考虑两个目标 . 给定所有边缘权重相等，如果它们在其大部分长度上共享单个最短路径，那么这优于两个大多数非重叠的最短路径（树中较少的边缘等于较低的总成本） . 另一个例子：两条路径长度的一小部分不... -
0 votesanswersviews
找到有向图的最短路径
对于 (u, v) ∈ E ，有一个有向图 G = [V ; E] ，边权重为 w(u, v) . 假设 {d[v], π[v]}; v ∈ V 和声明的值 这些是最短路径的长度和前一个节点的长度 它为 v ∈ V ，我怎么能验证这个语句是真还是假，不能从头开始解决整个最短路径问题？这是我遇到的一个问题，我头脑中的想法不多 . -
1 votesanswersviews
如何在等加权图中找到最短路径
我有一个如下图：节点之间的所有边都有距离= 1 . F | E | A-B-C-D | | G O | | H P | | I Q | | J R | | K-L-M-N 我必须找到从A节点到Q的最短路径 . 我使用的算法如下（借用维基百科）： 1 function Dijkstra(Gr... -
2 votesanswersviews
在图表中找到强制访问某些边缘的最短路径，而其他边缘则不是必须访问的
我有一个带有大约1000个节点和2000个边的无向图，一个起始节点和一个结束节点 . 我必须从起始节点遍历遍历所有强制边（大约10）的结束节点，而不必遍历所有顶点或节点 . 是否有一个简单的解决方案，就像现有的图遍历算法中的一些细微变化？我该怎么做？ 感谢帮助 . ：） 这个问题与Find the shortest path in a graph which visits certain node... -
4 votesanswersviews
带有彩色边缘的图形：最短路径，最多k个颜色变化？
我有一个带有彩色加权边的有向图 . 有2种颜色 . 每个边缘只能有1种颜色 . 我想找到颜色变化有限的最短路径 . 从一个顶点可以出现最多2个边缘，其中有2种不同的颜色，2个边缘有2种不同的颜色 . 例如，在此图中： 最短路径最多3个颜色变化 9 最大 0 颜色变化最短路径是 6+1+4=11 等 . 我的解决方案是递归访问所有可能的路径并交换，如果递归找到一个更好的，使这个问题呈指数级 . 是... -
12 votesanswersviews
算法：所有点之间的最短路径
假设我有10分 . 我知道每个点之间的距离 . 我需要找到通过所有点的最短路线 . 我已经尝试了几种算法（Dijkstra，Floyd Warshall，......），它们都给了我开始和结束之间的最短路径，但是它们没有制作一条包含所有点的路线 . 排列工作正常，但它们太耗资源 . 您可以建议我使用哪些算法来研究这个问题？或者是否有记录的方法使用上述算法执行此操作？ -
3 votesanswersviews
网格中两点之间的最短路径（Matlab）
我试图在没有障碍物的网格中找到两个点之间的最短路径并向所有方向移动（N NE E ES S SW W WN） . 这似乎是一项常见任务......这是否已在Matlab中实现？当Matlab绘制一条线连接的两个点（图（X，Y，' - '））似乎在内部进行计算，因为我猜测生成的图像也是网格 . 示例：从[1,1]到[3,6]，一个解是[1,1; 2,2; 2,3; 2,4; 3,5; 3,6] 我试... -
7 votesanswersviews
最短的路径，一个可跳过的边缘
我有这个问题：“具有一个可跳过边缘的最短路径 . 给定边缘加权有向图，设计 E*log(V) 算法以找到从 s 到 t 的最短路径，您可以将任何一条边的权重更改为零 . 假设边权重是非负的 . “ 我不明白他们要我做什么 . 将重量变为零意味着什么？我认为我可以将任何最短路径中的任何边缘改为零，它仍然是最短的 . -
0 votesanswersviews
在N步骤内的DIrected非循环图最短路径
我有一个问题，即在正加权有向无环图中找到最短路径，但是限制了最大N步数（路径中的边） . 假设路径存在 . 该图的附加属性是如果边（i，j）在图中，那么任何边（i，k）也在i <k <j的图中 . 我只对图的开始和结束之间的最短路径感兴趣（在拓扑排序之后） . 我知道有一种有效的算法用于O（V E）中有向无环图中的最短路径，但它没有考虑步长限制 . 我想不出任何方法可以使它成为O（（V... -
0 votesanswersviews
O（n ^ 2）算法在去除顶点后保留最短路径
如果我想构造一个O（n ^ 2）算法，该算法在移除顶点后保留图形的最短路径距离，我应该使用动态编程来处理这个问题，并且函数存储有关每个双数组框中最短路径的信息吗？ 例如，我有一个图G，我拿出一个顶点，然后得到新的图G2 . 我希望G2的所有顶点之间的最短距离等于原始G的最短距离 -
1 votesanswersviews
动态编程和Dijkstra
我正在阅读以下问题陈述，意在通过动态编程解决： 给定无向图G，其具有N（1 <N <= 1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 . 我相信算法应该是这样的 S = starting point N = ending poi... -
1 votesanswersviews
图中的最短路径
给定无向图G，其具有N（1 <N≤1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 . 我在topcoder上发现了这个问题，我认为应该使用Dijkstra的算法，但是帖子是关于动态编程的，而Dijkstra是一个贪婪的算法 . 谁能告诉我解... -
1 votesanswersviews
优化搜索具有N个顶点和N个边的图中的所有最短路径
我需要找到Graph G 中所有对之间的最短路径 . 我正在使用Floyd-Warshall算法来计算解决方案 . 我需要知道是否有更好的选择来找到关于 G 这些事实的所有最短路径： G 是无向图 . 顶点数和边数相同 . 所有边缘权重均为正值 . 鉴于这些事实，有没有比Floyd-Warshall更好的解决方案？ -
2 votesanswersviews
最短路径更快 - SPFA算法？
我正在实现一个k最短的顶点不相交路径算法，需要一个快速算法来找到最短路径 . 有负权重，所以我不能使用dijkstra和bellman-ford是O（ne） . 在我最近阅读的一篇论文中，作者使用所谓的SPFA算法来找到负权重图中的最短路径，根据它们，它具有O（e）的复杂度 . 听起来很有趣，但我似乎无法找到有关该算法的信息 . 显然这个：http://en.cnki.com.cn/Article... -
2 votesanswersviews
未加权图/树中两个给定节点之间的最短路径
我正在寻找一种算法，通过使用邻接矩阵来确定未加权图中两个节点之间的最短路径 . 我知道Dijkstra和Bellman - Ford，但没有找到特定于确定两个给定节点之间的最短路径 . 任何帮助都是非常有用的