问题标签 [dijkstra]

我必须在不使用斐波那契堆的情况下实现 Dijkstra 和 Sedgewick-Vitter 算法。有关 Dijkstra 完整互联网的信息，但我找不到 Sedgewick-Vitter 算法的伪代码或示例。我只发现 McHugh, Algorithmic Graph Theory book 中有一些信息，但我找不到免费的 pdf。所以也许有人知道这个算法并且可以分享信息、伪代码、链接？

干杯!

首先，请原谅我英语不好。

我遇到了以下问题：我必须以固定顺序（例如 A -> D -> F）找到 2 个以上点之间的最短路径。我熟悉 Dijkstra 的算法。但是那个只计算两点之间的最短路径。我也听说过 TSP，但这似乎也不合适。因为没有修复顺序。我已经在网上搜索了我的问题，但也许这不是一个很受欢迎的问题，或者我使用了错误的关键词。

尽管如此，还是要有一个解决方案，因为有很多路线规划器，都成功地提供了这个功能。

所以拜托，任何人都可以通过命名一个算法来帮助我解决我的问题，或者给我一些建议。

非常感谢您的帮助！你真诚的，安杰洛

//edit 呵呵，很尴尬。看来我想了很久，所以我没有描述真正的问题。就是这样：有一些票，只能从头使用。

T1：A -> B（费用 50） T2：B -> C（费用 50） T3：A -> B -> C（费用 80） 给定路线是 A -> B -> C

现在你看，如果我们将给定的路线视为两个独立的问题，我们的总成本将变为 100，但显然 Ticket T3 是更好的解决方案。

我的 Dijkstra 算法可以很好地找到路径。现在我想回去展示我走的路。我标记了一个访问过的顶点，并给它一个指向我来自“prev”的顶点的指针。不幸的是，当在 while 循环中循环时，这些指针会以某种方式被操纵，因此最后的顶点不知道它们来自哪里。你能帮助我吗？

可能这是我没有得到的指针问题。我有一个复制构造函数和一个 = 运算符。

如何对图应用 Dijkstra 算法以找到 MST，使得生成的树必须在两个给定顶点之间有一条边？（例如：MST 必须包含 X 和 Y 之间的边）

谢谢

问候。Dijkstra 写道，即使是几行看似简单的代码也可能令人绝望地模棱两可。在至少一个我现在找不到可以挽救我生命的作品中，他给出了一个小示例程序来证明这种模棱两可。任何人都可以指出他的一篇论文，其中包括其中一个例子吗？

我正在尝试在 Java 中实现 Dijkstra 的算法（自学）。我使用维基百科提供的伪代码（链接）。现在接近算法的结尾，我应该decrease-key v in Q;。我想我应该用 BinaryHeap 或类似的东西实现 Q ？在这里使用的正确（内置）数据类型是什么？

下面是我根据维基百科文章中的伪代码编写的 Dijkstra 算法的实现。对于具有大约 40 000 个节点和 80 000 条边的图，运行需要 3 或 4 分钟。这是正确的数量级吗？如果没有，我的实施有什么问题？

至少有几个答案建议使用 STL 堆函数来实现 Dijkstra 算法中的优先级队列：

Dijkstra 算法实现的性能

实现 Dijkstra 算法

鉴于 STL 不包含用于更新键的堆函数，对堆中的顶点重新排序（第 19 行）的最佳方法是什么？

我读过他的开创性论文，尽管有分布式控制，但仍能自稳定系统。但是，我不太明白自稳定算法的工作原理。我对他的 k 状态机“解决方案”最感兴趣。纸张的密度非常高，我无法理解它。这个算法在简单的英语中是如何工作的？

我正在尝试将 Dijkstras 算法写入我在下面编写的代码中。但我不确定如何开始这样做。我确实从在线资源中对其进行了一些审查，但我仍然不确定如何让它真正发挥作用。我更喜欢将其放入评估路径方法中。然后让菜单选项调用此方法并执行排序算法。

供参考。我正在按里程和价格对从城市 A 到城市 B 的最短路径进行排序。

下面是我的代码。

输出应如下所示::

从西雅图到旧金山的最短路线是 1290 英里。