-
5 votesanswersviews
使用 SPARQL 查询查找最短路径
我试图理解 SPARQL 查询的计算限制，我想知道如何编写一个查询来确定两个对象之间是否存在有向路径。 我知道如何为特定长度的路径执行此操作： SELECT ?a ?b ?c ?d WHERE { ?a <http://graphtheory/hasNeighbor> ?b . ?b <http://graphtheory/hasNeighbor> ... -
26 votesanswersviews
找到第k个最短的路径？
找到图中两点之间的最短路径是一个经典的算法问题，有许多好的答案（Dijkstra's algorithm，Bellman-Ford等） . 我的问题是，在给定有向加权图的情况下，是否存在一个有效的算法，一对节点s和t，以及值k，找到s和t之间的第k个最短路径 . 如果有多条相同长度的路径都与第k个最短路径相关，那么算法返回任何路径都是正常的 . 我怀疑这个算法可能可以在多项式时间内完成，但我知道可... -
-1 votesanswersviews
具有深度优先搜索的最短路径
如何使用DFS获取最短路径 . 我已经多次看过这个问题，但回复通常都是使用BFS或不同的算法 . 在机器人穿越迷宫的背景下怎么样？ BFS是不可能的，因为它从节点跳到节点，机器人需要回溯 . 现在我正在尝试使用以下方法解决问题： def dfs(self, v): v.visited = True for adj in v.adj: if adj.visited i... -
1 votesanswersviews
寻找多个点的最短路径
Requirements: 您需要在图表上访问多个目标（无论您访问每个点的顺序或次数都无关紧要） 您可以从起点开始，访问所有目标并返回基地 . 您可以多次访问每个目标 . Question: 1）我应该用什么算法来解决这个问题？ 2）我提议的方法 我们说目标= [A，B，C] 我正在考虑使用Dijkstra的算法来找到任何目标的最短路径 . 一旦我到达目标，我使用Dijst... -
2 votesanswersviews
R / Python / Matlab中具有动态权重（重复Dijkstra？距离矢量路由算法？）的图形最短路径
我有一个平均道路网络的图表 . 交通速度衡量一整天都在变化 . 节点是道路上的位置，边缘连接同一道路上的不同位置或两条道路之间的交叉点 . 我需要一种算法，它可以在给定开始时间的情况下解决任意两个节点之间的最短行程时间路径 . 显然，图表具有动态权重，因为边缘i的行程时间是该边缘处的交通速度的函数，这取决于您的路径到达边缘i所需的时间 . 我已经使用边权重=（edge_distance / edg... -
0 votesanswersviews
如何输入矩阵样式的txt文件，而不是为C定义我自己的int 2D数组
所以我对C很新，但我想我已经开始了解它 . 作为excersize的一部分，我必须采用输入文本文件并将其应用于“最短距离算法”，最终我想输出所有最短距离和路线，但我还没有那么远 . 我使用了Floyd Warshall算法 . 现在我的问题是，我如何用文本输入替换自编写的int数组 . 输入数组只是数字，但实际上表示节点之间的距离 . 我现在使用的测试阵列只有3个节点，但我希望能够将它扩展到更大的... -
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] [... -
2 votesanswersviews
找到网格上的点和行之间的最短路径
我知道有一些算法可以找到 two points 之间的最短路径，例如，在How to calculate the shortest path between two points in a grid中回答的算法 . 但是，现在，我有一个 N * M 网格，其中行从0到N-1，列从0到M-1，其中每个网格包含障碍物（或者您可以将其视为两个网格之间的距离） . 例如，我下面有一个4 * 4网格： 5 ... -
3 votesanswersviews
（Eucledian最短路径）检测平面中障碍物的角落
问题历史/原点 最近我偶然发现Twitch.TV上的 Channels 来自执行经典游戏速度的玩家 . 其中一人打了The Legend of Zelda - A Link to the Past . 我看到了很多低效的动作，我开始怀疑 - 鉴于世界 Map 数据 - 是否有可能编写一个执行完美速度的机器人 . 一个经常出现的子问题是找到一个平面中两点之间的最短路径，我认为这是一个非常有趣的问题，... -
21 votesanswersviews
最好的最短路径算法
"Floyd-Warshall algorithm" 和 "Dijkstra's Algorithm" 之间有什么区别，哪个最适合在图中找到最短路径？ 我需要计算网络中所有对之间的最短路径，并将结果保存到数组，如下所示： **A B C D E** A 0 10 15 5 20 B 10 ... -
1 votesanswersviews
最短路径不是图中的路径
我想知道是否有一种算法可以在图中找到最短路径 . 假设我有一个图表，其中有一对从一个顶点到另一个顶点的路径 . 这些路径中的两个或更多个具有相同的成本 . 如何标记，找到这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法将找到最短路径，但他们只“选择”一个 . -
3 votesanswersviews
消除两个顶点之间的所有最短路径
给定有向图 G=(V,E) ，两个顶点 s ， t 和两个权重函数 w1 ， w2 ，我需要在 s 之间的 s 到 t 之间的所有最短路径中找到 s 到 t 的最短路径 . 首先，我怎样才能找到两个顶点 s 和 t 之间的所有最短路径？ Dijkstra的算法帮助我们找到从顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？ -
0 votesanswersviews
删除边后对最短路径的影响
已经提供了有向图的输入，并且我已经使用 - 异步和同步Bellman-Ford算法找到了到特定节点'T'的最短路径 . 我试图在删除一些边缘后找出最短路径上的效果 . 在我的方法中，我试图将删除边缘的起始节点处的距离标记为无穷大，并且尝试应用异步Bellman-Ford，但我陷入困境，因为其他节点不会更新它们的值，因为它们已经是最短的路径最小值 . 任何人都可以帮我找到一种方法来找到新的最短路径而... -
-1 votesanswersviews
哪个python包实现了Bellman-Ford最短路径算法？ [关闭]
哪个python包实现了Bellman-Ford最短路径算法？ 给定起始节点i和具有负权重的邻接矩阵G，我想找到从i到另一个节点j的最短路径 . 例如 . 我的图表看起来像： import numpy G = numpy.array([[ 0. , 0.55, 1.22], [-0.54, 0. , 0.63], [-... -
-1 votesanswersviews
最短路径算法成本计算
所以问题是这样的：给出有向图G =（V，E）和权重函数wt：E-> R.您还会得到两个不同的节点s，t∈V写一个算法，该算法标记每个节点v，使得v位于从s到t的最短路径上 . 也就是说，为每个节点引入一个布尔字段v . 你的算法应该 Build 后置条件：∀v∈V：v.on≡（∃p：shpath（p，s，t）∩沿（v，p））我们定义shpath（p，s，t）=路径（p，s，t）∩wt（p）=... -
0 votesanswersviews
如何使用广度优先搜索找到迷宫中的最短路径？
我已经多次问过这个问题，但我只是想了解如何将其置于上下文中 . 我试图找出如何使用广度优先搜索找到迷宫中的最短路径 . 我已经获得了一个创建迷宫的程序，我正试图找到通过它的最短路径 . package solver; import java.awt.Point; import java.util.LinkedList; import java.util.List; import java.uti... -
17 votesanswersviews
找到通过一些任意节点序列的最短路径？
在this earlier question中，OP询问如何在图中找到从u到v的最短路径，并且还通过某个节点w . 接受的答案非常好，就是运行Dijkstra 's algorithm twice - once to get from u to w and once to get from w to v. This has time complexity equal to two calls to... -
4 votesanswersviews
用Dijkstra算法找到哈密顿路径？
Dijkstra算法可以找到从单个源顶点到所有其他顶点的所有最短路径，这样路径就可以访问无向和对称图形中的所有顶点一次并且恰好一次吗？对称图有更快的算法吗？ -
1 votesanswersviews
在包含至多两个负边的图中查找最短路径距离
我得到了一个有向图，其中每个边都有成本 . 利用图中最多有两个负边的事实，我的目标是找到从给定节点到V中所有节点的最短路径距离 . 算法的时间复杂度应该是 O(|E| + |V|*log|V|) ，所以我认为我需要应用Dijkstra的算法 . 我猜我需要将我的给定图形以某种方式转换为具有非负权重的新图形，该图形中从s到v的最短路径将等于给定图形中所需的最短路径...或者我可能需要修改Dijkst... -
2 votesanswersviews
通过墙找到最短路径的算法
我正在为一个基于文本的游戏编写AI，我遇到的问题是我如何确定如何确定墙的最薄部分 . 例如，以下代表2D Map ，其中'^'是想要通过'*'字符表示的墙到达标记为'X'的位置的字符： ------------------ | X * | |***** | |**** | |*** | |** ^ ... -
2 votesanswersviews
连续空间最短路径
我需要一个最短路径算法来控制现实生活中的机器人 . 假设我有一个矩阵形式的环境 Map ，其中1是障碍物，0是自由空间 . 如果我使用传统的最短路径算法，例如A *那么这将给我一个曼哈顿距离最短路径 . 所以没有实际的最短路径 . 出现这个问题是因为我无法想到一种以对角线优于两条直线的方式来惩罚运动的方法 . 我可以制作一个启发式算法，首先让A *尝试两个点之间的欧几里德最短路径，但实际上并不能使... -
103 votesanswersviews
使用Dijkstra算法的负权重
我试图理解为什么Dijkstra的算法不适用于负权重 . 阅读Shortest Paths上的示例，我试图找出以下场景： 2 A-------B \ / 3 \ / -2 \ / C 来自网站： 假设边缘全部从左向右指向，如果我们从A开始，Dijkstra算法将选择最小化d（A，A）长度（边缘）的边（A，x），即（A，B） . 然后设置d（A，B）= 2并选择另一个... -
1 votesanswersviews
寻找迷宫中最短路径的地雷和有限的生命
我遇到了一个问题，我在解决方面遇到了一些麻烦 . 我正在尝试编写一个程序来解决一个m网格迷宫，其中有地雷 . 棘手的部分是玩家/迷宫跑者的生命数L> = 1，这意味着他们可以踩下最多的L - 1地雷，然后才能在下一枚地雷上死亡 . 更多详情： 每个单元可以连接到任何相邻单元 . 所有连接都是双向的 . 我们可以假设迷宫在给定生命数量的情况下从开始到结束都有正确的路径 . 迷宫... -
2 votesanswersviews
图中最长的圆圈
我想解决以下问题： 我有一个DAG，其中包含需要完成的城市和工作 . 这些工作适用于可以加载限定的卡车 . 卡车装载得越多，旅行就越好 . 有些工作用于加载某些东西，有些用于加载已定义的东西 . 即使在他们之间没有工作要做，你总是可以从城市a开车到b . 最后一个限制是我总是需要从城市a开始并返回到a，因为有卡车的家:) 我首先想到了Dijkstra的最短路径算法 . 我可以很容易地把它变成最长的... -
2 votesanswersviews
无向完整图中的最短路径？
我有一个问题可能很简单但是当截止日期即将来临时，大脑停止工作，所以有： 我有一个带有N个节点的无向完整图 . 我有一个起始节点，我有从每个节点到其他节点的距离矩阵 . 我想运行Dijkstra的算法或任何其他算法，以便找到从起始节点访问所有节点的最短方法 . 我想只访问每个节点一次 . 我相信这是一个完整的图表，每个节点连接到其他节点的事实会使问题变得容易，但我无法绕过编码 . 我正在使用C＃ .... -
2 votesanswersviews
找到给定源和一组目标之间的最短路径
您将获得一个加权连接图（20个节点），所有边都具有正权重 . 我们有一个从A点开始的机器人，它在例如B，D和E点通过 must . 我们的想法是找到连接所有这4个点的最短路径 . 机器人也有一个有限的电池，但它可以在某些点充电 . 在互联网上研究后，我有两个算法： Dijkstra's 和 TSP . Dijkstra's 将找到节点与每个其他节点之间的最短路径， TSP 将找到连接所有点... -
1 votesanswersviews
图中的最短路径（如何返回原点？）
我正在为一家运输公司做一个项目 . 基本上，我得到了200辆城市和7辆卡车，我需要计算7辆卡车的最佳重量分布和最短路径（km） . 在我实际与Google Maps API进行通信之前，我会自行计算 . 对于7辆卡车，我可以在大约2小时内计算出大约30万条路线 . （重量分布通过回溯/动态编程完成，“下一个城市”选择一些数学公式） 我需要比较这些路线并记住最好的路线（7辆卡车上最小的公里） . ... -
0 votesanswersviews
使用Dijkstra在加权有向图中找出最低权重循环
嗨，我正在努力解决这个问题 . 它是以下内容： 设计算法以在加权有向图G =（V，E）中找到最低权重周期（即图中所有周期，边缘权重之和最小的周期） . 简要说明运行时和空间复杂性 . 假设所有边都是非负的 . 它应该在O（| V || E | log | V |）时间运行 . 提示：使用Dijkstra算法的多个调用 . 我见过使用Floyd-Warshall的解决方案，但我想知道我们如何使用... -
6 votesanswersviews
用于找到最小化两个节点之间的最大权重的路径的算法
我想乘车从X市到Y市 . 我的车有一个小水箱，加油站只存在于道路交叉口（交叉口是节点，道路是边缘） . 因此，我想采取一条路径，使我在两个加油站之间行驶的最大距离最小化 . 我可以使用什么有效的算法来找到该路径？蛮力是一个糟糕的解决方案 . 我想知道是否存在更有效的算法 . -
3 votesanswersviews
如何获得最强的路径序言？
我正在尝试创建一个社交图，我必须编写一些Prolog才能获得最小和最强的路径 . 我的知识库只有以下声明： 边缘（来源，目的地，重量） 例如：（john，mary，2） . 权重现在只能为3： 1 - 朋友2-亲密的朋友3 - 家庭 这是我的最小路径代码（加权较少） . findapath(X, Y, W, [X,Y], _) :- edge(X, Y, W). findapath(X, Y,...