问题标签 [shortest]

我正在尝试实现一个室内导航系统，我必须找到从我当前位置到某个点的最短路径。

我已经达到的目标：使用 Dijkstra 的算法/Hipster 和一个测试代码，我在其中定义了 4 个具有权重的节点，然后尝试找到从源到目的地的最短路径。

现在的情况是，如果假设我在地图上的一个未定义为节点的点，并且我想导航到一个可能是也可能不是节点的点，那么在这种情况下如何找到最短路径？

我正在使用的当前测试代码：

我正在一家机构为 NEO4J 做 coursera 课程。

我注意到路径和长度以及海岸路径的示例都在我的机器上显示出与课程笔记/讲座中不同的结果。

我正在使用 3.0.6。有错误吗？我注意到它似乎无视边缘的方向。可能是我需要设置的一些设置吗？

提前致谢

加载

这是我作业的一部分，即在 ax,y 图中找到两点之间的最短路径（图的大小为 640*340。）。路径应该只通过 (X,Y) 值是整数的点。我是 C++ 新手，但是老师告诉我们我们已经用 C++ 编写了代码。我的代码如下：

基本上我想找到所有 (s,t) 对的最短路径，但有几个考虑因素。例如，网络包含几个集群/社区或节点组。这些组将是预定义的，并且节点数量可能相对较大。

我想找到遍历至少一个节点的所有 s,t 对的最短路径，例如来自 gourp1。在一般情况下，如果我只有一组节点，则问题会简化为传统的中介中心性。稍后我想为所有 s,t 对找到从 gourp1 和 group2 遍历至少一个节点的最短路径。

有什么建议么？

谢谢！:)

这是我的 BFS 算法，我问这个问题的主要原因是因为与我自己的问题类似的其他问题往往是用向量来完成的。我还没学过向量。我想要做的是使用 ' ' 字符打印最短路径以将其显示在有效元素上。它应该在界限内，没有访问过墙（墙是'#'字符），并且不应访问两次任何元素。我知道如果我正确设置了我的前身二维数组，最短路径应该会正确显示。但是，我不确定我是否正确设置了它以及如何用' '字符实际填充该路径......

我有一个位置及其经纬度信息

和由五个纬度对给出的路线（折线）

loc有没有一种简单的方法来计算以公里为单位的最短距离route？

首先，这是一个评估，我不是在寻找直接的答案，而是在寻找最佳解决方案的复杂性，正如您所想的那样。

这是矩阵中两个点（起点和终点）之间的最短路径的已知问题，同时有障碍物。移动可接受的是上、下、左和右。假设移动时 i 携带某物，每次移动的成本为 2 。矩阵中有一些点（我们将它们命名为 B 点），我可以将它留在一个 B 点中，然后从另一个 B 点拾取它。在 B 点倾倒某物的成本是 1，从 B 点重新捡起某物的成本是 1。每当我没有这个东西搬家时，我现在搬家的成本是1。我认为解决方案是将矩阵转换为树并应用 BFS。然而，这在没有 B 点的情况下有效。

每当我考虑到 B 点复杂性时，就会出现最坏的情况 N^2。这是一个例子：

S = Start , E = End , B = B point to drop sth, O = 障碍 所以我从 S 开始向下移动到 B 点 (2*2=4 点) 离开 sth 在 B 点 (1 点) 移动右右（2*1=2分），捡起来（1分），下移2分=共10分。

我认为是用每个 B 点的节点构建树，但是这将创建一个几乎 (V-1)*(V-1) 边缘的非常密集的循环图，它采用 N^2 边界中的算法来创建图. 这是上面最坏的情况：

我认为的另一个选择是首先计算没有 B 点的最短路径。然后在每次迭代中进行迭代：首先在 S 上有 bfs，在最近的 B 在 E 和最近的 B 上有 BFS 然后看看在最接近 S 的 B 和最接近 E 的 B 之间是否有路径。如果有，那么我会看看路径是否小于有障碍物的常规最短路径。如果它更大，那么就没有最短路径（没有贪心测试）。如果 2 个 B 点之间没有路径，请尝试第二个最接近 S 的点，然后重试。如果再没有路径，第二个最接近E，最接近S。但是，在最坏的情况下，我无法计算这一复杂性，而且没有贪婪的测试来评估它。

`使用此代码时出现堆栈溢出错误。如果我们已经找到最短路径，我希望它可以工作，然后递归代码将停止。迷宫包含字符“#”和“”。如果我找到了最短路径，该路径将标有“。” 请帮忙谢谢。

我想编写一个简洁的代码来计算点与任何方向上的任何线段之间的最短距离。我知道在许多情况下，最短距离是从点到线段的垂直线，在某些情况下，是连接线段两端点的线（以较小者为准）。

我已经完成了研究并编写了一些代码！结果并不完全正确，如下图所示，其中红线在每次迭代中的长度都会发生变化，并且计算从星到每条线的最短距离，以获得距离的分布。正如您所看到的，对于某些线段，应该垂直的最短距离实际上并非如此。

我编码的方式是使用d=sqrt((xstar-xline)^2+(ystar-yline)^2)然后最小化它，xline并考虑每个线段的x端坐标，获取xline然后yline将星连接到线上的那个点，但是可以看出它看起来不正确.

任何人都可以通过发布代码或伪代码或算法来提供帮助吗？

问题还没有解决！

请考虑附图中的左上角线段：

而且我使用了与答案中提到的完全相同的算法，但最短距离似乎仍然不正确，因为它没有连接P到B！

我想在矩形的每个左右进行迭代并使用 line 连接它并选择最短的线，如（左图）this 。然后我想得到与轮廓线相交的位置（右图）。有人知道解决方案吗？