Dijkstra算法使用2D数组

Question

在过去的几天里，我一直在尝试实现这个算法。到目前为止，我已经成功创建了一个动态的二维数组，并插入了节点之间的距离，创建了一个删除节点之间路径的函数，以及一个告诉我两个节点之间是否有路径的函数。 现在，我想要实现一个函数，该函数从节点A到节点B返回最短路径。我知道Dijkstra算法的工作原理，并且已经阅读了维基百科上的伪代码，但是我无法自己编写任何代码。我真的卡住了。

我一直在思考代码应该是什么样子以及会发生什么，这就是我制作那个告诉我是否存在两个节点之间路径的函数的原因。我需要任何更多的辅助函数来更轻松地实现Dijkstra吗？

目前我只有3个节点，但我希望编写的代码可以适用于n个节点。

感谢任何形式的帮助。

- ogward

Answer 1

你可能想太多了。你需要两个东西：一个干净的图形结构，你能理解；一个好的算法描述，你也能理解。如果两者都有了，就开始写一些代码吧。在路上会遇到需要帮助的地方。

-- 编辑 --
你可能需要以下一些数据结构：
std::vector std::list std::priority_queue

- log0

Answer 2

我发现了几个关于该算法的代码，但是可能最简单的代码会更好地帮助你理解它，这样你可以查看你的代码和这个代码之间的差异，并完善你的代码。编写自己的代码总是更好的选择。

请看下面的代码，看看它是否有所帮助。 http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/ 祝你好运。

- Jav_Rock

Answer 3

编辑: 代码已删除，我将给出提示：

1. 将图存储为每个顶点的邻接列表。 (类似于这样的 vector < vector < pair<int,int> > > g (n);)
2. 使用某些数据结构来跟踪当前状态中具有最小距离的顶点。 (可能是 set 或 priority_queue，以实现 O(m log(n)) 复杂度)
3. 每次取高优先级顶点 (具有最小当前距离的顶点)，从您的数据结构中删除它并更新与删除的顶点相邻的顶点的距离。

---

注意: 如果您还想获得最小路径，则保持一些 vector<int> previous，每次更新顶点的距离时设置 previous[v] = 来到这里的顶点的索引。 您的路径是反转顺序的 last, prev[last], prev[prev[last]],...,first。

- Mihran Hovsepyan

---

@Mihran - OP明确标记了这是一道作业问题。直接给出解决方案是非常不好的做法。你应该提供如何继续的提示。 - Mahesh

感谢您的回复。 问题是我从未使用过向量，因此不知道如何使用它们。我可以用其他方法吗？ 现在我有一个二维整数数组，其中包含节点之间的距离和一个包含城市（节点）的字符串数组。 还提到了优先队列，C++有一个“标准”容器吗？我只知道如何使用列表实现pq。 - ogward

优先队列是非常重要的数据结构 - 以堆为简单例子进行学习。然而，现在不需要担心它们（特别是因为您现在正在处理向量）。在 Dijkstra 算法中，您需要能够高效地重新计算队列中的项目成本，而“标准”的堆操作（在 STL 算法包中）仅处理插入和删除。但是堆非常简单，因此（只要使用第二个向量允许快速访问堆中的节点，并适当维护它），您可以自己制作冒泡上升和冒泡下降过程。 - hugomg

我真的不确定如何使用向量，我尝试使用数组来修复它。这就是我得到的，不知道是否正确。 链接 不知道为什么格式会这么糟糕。 - ogward

@ogward，您能否请发布您的代码？我会检查并告诉您问题所在。 - Mihran Hovsepyan

@ogward，你的Graph类中保存了什么？this->nrOfCities是什么？this->connection是什么？你能否请发布Graph类的完整代码？ - Mihran Hovsepyan