问题标签 [dijkstra]

我在哪里可以找到 C 中的 A* 实现？

我环顾四周，但似乎我的 google-fu 不够强大。我已经开始编写自己的实现，但后来我想起了 Stack Overflow，我想我应该先在这里问一下。编写一个真正的 A* 实现似乎有点复杂- 我很想只为二进制网格编写 Dijkstra 算法的实现，因为这就是我真正需要的，但我觉得我想在我的曲目。

我正在阅读Coders at Work。

我在 Donald Knuth 的采访中看到了这一段。

Seibel：似乎很多与我交谈过的人在刚开始时都可以直接使用机器。然而Dijkstra 有一篇我相信你很熟悉的论文，他基本上说我们不应该让计算机科学专业的学生在最初几年的培训中接触机器。他们应该把所有的时间都花在操纵符号上。

我想要那篇论文的链接。那是哪一张纸？（他写的太多了:-)

在过去的四天里，我试图了解 dijkstra 的算法。但我不能。我有一个点向量。由此我创建了一个成本矩阵。但我不知道如何制作dijkstra的算法。资源可在网上获得，但我不是计算机科学背景，所以我无法理解它们。我正在尝试制作这样的功能

如果有人，可以请您发布代码。我并不懒惰。但是我的项目在一天前就已经超过了截止日期。现在我失去了理解逻辑的希望。现在只是我想要的功能。“患难见真情”。

编辑：特别感谢“Loki astari”的出色回答

我在程序中使用 Dijkstra 算法。假设我有一个带有顶点和边的图。如果我们想象从源顶点“a”开始的所有边如下所示

并且所有以顶点“f”结尾的边是：

我从一开始就需要知道的是，我希望边缘a-->b作为我的起始边缘（假设“a”作为起点）所以不需要搜索“a”的其他邻居，即(a-->c and a-->d)

此外，我只想要以m-->f结尾的路径（假设“f”为目的地），即我不希望路径包含b-->f,m-->f,e-->f,w-->f

那么修剪我的初始图是不是一个好主意，因为它不包含这些边，然后在上面应用 Dijkstra？

实际上找到这些边缘需要一些搜索。我想知道是否值得（考虑时间或 CPU 使用率）进行搜索和修剪我的图表，还是有更好的方法？

我正在开发一个可以查找公交路线的离线 C# 应用程序。我可以提取时间表/巴士/路线数据。我正在寻找适用于基本数据的最简单的解决方案。

什么算法可以用来找到从巴士站“A”到巴士站“B”的路线？是否有适用于 C#/Java 的开源解决方案？用于数据库的 google GTFS 格式是否适合简单的解决方案？http://code.google.com/transit/spec/transit_feed_specification.html

谢谢你的帮助。我被这个困住了。我不知道从哪里开始——如何存储数据以及如何查找路线。我知道 Dijkstra/A*，但我只在不依赖时间的图表上使用它们......

我需要一些关于 Dijkstra 在 C 中的算法的帮助。

我已经生成了我的邻接矩阵，看起来像：

我找到了这个实现：http ://www.answers.com/topic/dijkstra-s-algorithm-1但路径是一维数组，我的矩阵是二维数组。

有没有办法将一个转换为另一个？或者也许有人有处理这种矩阵的方法。

提前感谢您的帮助

在“算法简介，第 3 版”练习 24.3-5 中想要一个例子说明这是错误的（并不总是正确的）。那可能吗？在我看来，这是不可能的，因为在已经确定了到当前顶点的路径时，每条边都会放松。

一个字一个字地：

N. 教授声称拥有 Dijkstra 算法正确性的证明。他声称 Dijkstra 的算法按照它们在路径上出现的顺序松弛了图中每条最短路径的边，因此路径松弛特性适用于从源可到达的每个顶点。证明教授错误地构造了一个有向图，Dijkstra 的算法可以针对该有向图放宽最短路径的边缘无序。

我需要使用（而不是实现）基于数组的 Dijkstras 算法版本。任务是给定一组线段（障碍）和起点/终点，我必须找到并绘制从起点/终点开始的最短路径。已经完成了计算部分等。但不知道如何在我的代码中使用 dijkstras。我的代码如下

现在我有了从每个 segmnet 到所有其他段的距离，amd 使用这个数据（在 neighbourinfo 中）我想使用基于数组的 Dijkstras（restriction）来追踪从起点/终点开始的最短路径。有更多代码，但有为方便读者缩短问题

请帮助！谢谢，请不要.net lib/code，因为我只使用核心C++ ..提前谢谢

但我需要基于数组的版本（严格..）我不打算使用任何其他实现。

两者都可用于从单一来源中找到最短路径。BFS 运行于O(E+V)，而 Dijkstra 运行于O((V+E)*log(V)).

此外，我还看到 Dijkstra 在路由协议中的使用非常相似。

因此，如果 BFS 可以更快地做同样的事情，为什么还要使用 Dijkstra 算法呢？

我在一次采访中被问到这个问题，但我想不出任何合适的解决方案。所以，我告诉他们找到所有周期然后选择长度最短的周期的幼稚方法。

我很想知道这个问题的有效解决方案是什么。