5

在过去的几天里，我试图实现这个算法。到目前为止，我已经设法制作了一个动态二维数组并插入节点之间的距离，一个删除节点之间路径的函数以及一个告诉我两个节点之间是否存在路径的函数。现在我想实现一个函数，它返回从节点 A 到节点 B 的最短路径。我知道 dijkstras 算法是如何工作的，并且我已经阅读了 wiki 上的伪代码，但我自己却无法编写任何代码。我真的被困在这里了。

我一直在考虑代码应该是什么样子以及应该发生什么，这就是为什么我制作了那个告诉我两个节点之间是否有路径的函数。我是否需要更多帮助功能来简化 dijkstras 的实施？

目前我只有 3 个节点，但我想编写的代码通常需要适用于 n 个节点。

任何形式的帮助表示赞赏。

4

3 回答 3

5

你可能想多了。

你需要两件事。你理解的一个干净的图形结构。对您理解的算法的良好描述。如果你两者都有。刚开始写一些代码。需要的助手将在途中变得明显。

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

于 2011-05-10T07:03:35.803 回答
2

我找到了这个算法的几个代码，但也许最好是最简单的一个，以便更好地理解它，所以你可以检查你的和这个之间的差异，并完成你的。以自己的方式编程总是更好。

看看这个，看看它是否有帮助。

http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

祝你好运。

于 2011-05-10T07:01:56.277 回答
2

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

  1. 将图存储为每个顶点的邻接列表列表。（像这样vector < vector < pair<int,int> > > g (n);）
  2. 使用一些数据结构来跟踪当前状态下距离最小的顶点是什么。（可能设置，或priority_queue 有O(m log(n))复杂性）
  3. 每次取 high_priority 顶点（当前距离最小的顶点），将其从数据结构中删除，并更新与已删除顶点相邻的距离。

注意：如果您还想获得最小路径，请在vector<int> previous每次更新顶点距离（例如v）时保留一些previous[v] = index of vertex from where you came here。你的路径是last, prev[last], prev[prev[last]],...,first相反的顺序。

于 2011-05-10T07:02:05.507 回答