问题标签 [shortest-path]

在图论中，最小距离（Dijkstra 算法发现）和最小路径（我不确定它是什么）之间的区别是什么？

在研究跨网络的最短路径算法时，我想生成网络的图片。我想表示节点（圆）、链接（线）、遍历链接的成本（链接线中间的数字）和链接的容量（链接线上它代表的节点旁边的数字）在图片里。是否有任何库/软件可以帮助自动创建此图片？

我可以在 Visio 或使用某些绘图应用程序中手动执行此操作，但我想在更改/调整网络时从代码生成它们。

我正在使用带有无向和未加权边的 adjacency_list 图。我需要找到顶点 u 和顶点 v 之间的最短路径。我应该从 u 开始使用 breadth_first_search() 吗？到达v时，如何获取路径，如何停止搜索？

谢谢！

信息：我有一个 100 个节点的数组，[0 .. 99]。每个节点可以有任意数量的链接节点：

eg1, 0 链接到 5, 10, 15, 20. eg2, 1 链接到 30, 40, 50. eg3 等等。

所有 100 个节点都至少有一个链接节点，节点不知道谁链接到它们。

问题：如果提供了 START 和 END，我如何找到最短的链接路径。

例如。START=5，END=80，链接路径（示例）：[5]->10->24->36->[80]？

我正在使用 Pascal 和/或 PHP，但了解我在寻找什么 [代码也有帮助]。

我有一个AdjacencyGraph<string, Edge<string>>我想运行AlgorithmExtensions.ShortestPathsDijkstra的，但 QuickGraph 文档不是最好的。

有人有我可以效仿的例子吗？

我在谷歌上找到的所有东西都使用了观察者，这AlgorithmExtension并不需要。

我需要一个节点的有向循环图的最短路径示例（它应该从将成为输入的节点到达图的所有节点）。

请如果有一个例子，我需要它在 C++ 或算法中。

有一个 KSPA 的自定义实现需要重新编写。当前实现使用修改后的 Dijkstra 算法，其伪代码大致解释如下。我认为它通常被称为使用边缘删除策略的 KSPA。（我是图论的新手）。

据我了解该算法，为了获得第 k 条最短路径，将在每个源-目的地对之间找到“k-1”个 SPT，并且对于每个组合同时删除一个 SPT 中的每个“k-1”个边。显然，该算法具有组合复杂性，并且在大图上阻塞了服务器。人们向我推荐了 Eppstein 的算法（http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf）。但是这份白皮书引用了一个“有向图”，我没有看到提到它只适用于有向图。我只是想问这里的人们是否有人在无向图上使用过这个算法？

如果没有，是否有好的算法（就时间复杂度而言）在无向图上实现 KSPA？

提前致谢，

从 sdk 3.0 开始可以轻松使用 iPhone 中的 GPS 功能，但明确禁止使用 Google 的地图。我认为这有两个含义：

1. 您必须自己提供地图
2. 您必须自己计算最短路线。

我知道计算最短路线多年来一直困扰着数学家，但汤姆汤姆和谷歌都做得很好，所以这个问题似乎已经解决了。在网上搜索，我自己不是数学家，我遇到了Dijkstra 算法。有没有人在 iPhone 的类似地图的应用程序中成功使用过这个算法？您愿意与我/社区分享吗？这是正确的方法，还是其他选择？非常感谢您的考虑。

我正在尝试为清晰地图的吃豆人游戏提出一个好的和快速的启发式方法。

我的启发式方法是尝试计算 pacman 到达地图上每个点的食物所需的最小距离。我目前的算法基本上是 Prim 的 MST，它可以让我获得 O(n logn) 的运行时间，但不考虑 pacman 需要跟随边缘吃东西以及返回到前一个顶点的情况......

有更好的吗？

换一种说法：不用提笔连接几个点的最低成本是多少？

谢谢

我用队列实现了 Bellman - Ford 算法的解决方案，并将其性能与 Dijkstra 算法进行了比较。它们非常接近，这对我来说是一个惊喜，因为 Bellman - Ford 的复杂性是 O(NM)。我知道复杂性是针对最坏情况的，但结果仍然令人惊讶。我搜索了有关 Bellman - Ford 的一些信息，但我在 Sedgewick，Java 中的算法中只找到了这句话“在真实网络上，Bellman-Ford 算法通常在线性时间内运行”。你能给我解释一下贝尔曼 - 福特算法的性能行为吗？