问题标签 [shortest-path]

这是我正在使用的dijkstra结构:(但是MAXV（最大顶点数最大为500，每次我尝试将其更改为比这更多的东西时，它会在运行时生成并出错）

- 我想用这种方式来表示一个有 10000 个顶点的图，有谁知道如何优化它？

这是我的dijkstra代码：

此代码是我从算法设计手册书中构建的代码，但我无法编译它，因为我对指针的经验很少我认为这是我认为我无法编译它的主要原因：

如果有人可以在 djikstra 中进行一些更改，以使其通过当前配置的堆。

我了解到谷歌地图有一个获取方向的功能，可以让用户找到从一个点到另一个点的最短路径。Google 使用什么搜索算法进行此搜索？这个算法是否可以在 Android 平台上实现，知道它内存低并且在 Java 中运行（往往很慢）？提前致谢！

“ A graph with 6 vertes and 7 edges where the vertex no 6 on the far-left is a leaf vertex or a pendant vertex. ”的链接上显示的图有 DIAMETER 4？对还是错？

定义是

图的直径是图中任意顶点的最大偏心率。也就是说，它是任何一对顶点之间的最大距离。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径中任何一条的最大长度是图形的直径。

具有 N 个节点的网络的直径 D 定义为网络中任意两个节点之间的最大最短路径

具有 N 个节点的网络的直径 D 定义为任意两个节点之间的最短路径 D ¼ max (minp[pij length( p)) 中的最长路径 p。在这个等式中，pij 是节点 i 和 j 之间的路径长度，长度 (p) 是返回路径长度 p 的过程。例如，4 4 Mesh D ¼ 6 的直径。

嘿，我遇到了一个问题，我基本上得到了一张任意大小的网格纸，并且必须仅使用页面上每个网格点的坐标来开发距离矩阵。

我认为最好的方法是用于最短路径对的 Floyd-Warshall 或 Djikstra 算法，但不知道如何使其适应坐标距离，因为所有文档都使用预先确定的距离矩阵。所以任何帮助都会很重要

有一个博物馆组织为 NxN 房间。部分房间上锁且无法进入。其他房间是开放的，有些房间有警卫。守卫只能通过开放的房间和博物馆内的南北东和西移动。对于每个房间，找出到警卫的最短距离。你的算法的时间复杂度是多少？

I am working on a project that i must traverse a maze using the left-hand rule and based upon the intersections the program comes upon i need to create a node to connect to a graph that I will then determine the shortest path. The goal is for the program to run through the maze then close out the program and read from a file that contains the graph and determines the shortest path to the finish. what i have done is i can traverse the maze using the left-hand rule. what im thinking to do is create a node when i find the intersection and there after every time the program moves i increase the cost of that path by one. on a side note do you need to have an adjacency matrix when use dijkstra's algorithm?

我想知道是否有一种算法可以在图中找到最短路径。

假设我有一个图，其中有几条从一个顶点到另一个顶点的路径。这些路径中的两个或多个具有相同的成本。如何标记、查找等这些顶点之间的所有最短路径？据我所知，Dijkstra 或 Bellman-Ford 算法会找到最短路径，但他们只“选择”一条。

我的要求很高，与语言无关。

路线查找（如在 Google 地图“获取路线”或 GPS 中找到的）如何工作？我不敢相信它会尝试每条可以想象的路线并选择最短/最快等。必须有某种合乎逻辑的方法来找到给定起点和终点的最佳路线。

任何形式的解释都会很棒。

我正在实现双向 A* 搜索（双向搜索，因为搜索是同时从起点和终点执行的，当这两个搜索相遇时，我将获得最短路径 - 至少加入一些额外的逻辑）。

有没有人有任何使用单向 A* 和双向化（！）它的经验 - 我可以期待什么样的性能提升？我估计它或多或少地将搜索时间减半，至少 - 但我可以看到更大的收益吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这有任何相关性（我已经阅读了 MS 的“Reach”算法，但想朝着这个方向迈出一小步，而不是直接跳进去）。