使用二维数组的 Dijkstra 算法
在过去的几天里，我一直在尝试实现这个算法。到目前为止，我已经成功创建了一个动态二维数组并插入节点之间的距离，一个删除节点之间路径的函数以及一个告诉我两个节点之间是否存在路径的函数。 现在我想实现一个函数，返回从节点 A 到节点 B 的最短路径。我知道 dijkstras 算法是如何工作的，并且我已经阅读了 wiki 上的伪代码，但无法自己编写任何代码。我真的被困在这里了。
我一直在思考代码应该是什么样子以及应该发生什么，这就是为什么我创建了这个函数来告诉我两个节点之间是否存在路径。我是否需要更多帮助功能来使 dijkstras 的实施变得更容易？
目前我只有 3 个节点，但我想要编写的代码通常需要在 n 个节点上工作。
任何形式的帮助表示赞赏。
For the past few days I've tried to implement this algorithm. This far I've managed to make a dynamic 2d array and insert the distances between nodes, a function to remove a path between nodes and a function that tells me if there is a path between two nodes.
Now I would like to implement a function that returns the shortest path from node A to node B. I know how dijkstras algorithm works and I've read the pseudo code on wiki without being able to write any code my self. I'm really stuck here.
I've been thinking about how the code should look like and what should happen thats why I've made that function that tells me if theres a path between two nodes. Do I need any more help functions which would make implementing of dijkstras easier?
For now I have only 3 nodes but the code I would like to write needs to work in general for n nodes.
Any kind of help is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你可能想得太多了。
你需要两件事。您理解的干净的图形结构。对您理解的算法的良好描述。
如果你两者都有的话。开始编写一些代码。所需的帮助者将在途中变得显而易见。
-- 编辑 --
您可能需要以下一些数据结构
std::vectorstd::liststd::priority_queueYou are probably thinking to much.
You need 2 things. A clean graph structure you understand. A good description of the algorithm you understand.
If you have both. Just start writing some code. Helpers needed will become obvious on the way.
-- edit --
You will probably need some of the following datastructures
std::vectorstd::liststd::priority_queue我找到了这个算法的几个代码，但也许最简单的一个更好，以便更好地理解它，所以你可以检查你的代码和这个算法之间的差异，并完成你的代码。按照自己的方式编程总是更好。
看看这个，看看是否有帮助。
http://vinodcse.wordpress。 com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/
祝你好运。
I found several codes for this algorithm, but maybe it is better the simplest one in order to undertand it better, so you can check the differences between yours and this one, and complete yours. It is always better to program your way.
Have a look at this one and see if it helps.
http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/
Good luck.
编辑：代码已删除，我将给出提示：
向量<向量<对>>>g（n）; ）O(m log(n))复杂度）注意：如果您还想获得最小路径，请保留一些
vector。 previous 以及每次更新顶点距离（例如v）时，设置previous[v] = 来自此处的顶点索引。您的路径是last, prev[last], prev[prev[last]],...,first以相反的顺序。Edit: Code deleted, and I'm going to give hints:
vector < vector < pair<int,int> > > g (n);)O(m log(n))complexity)Note: If you want to get minimal path as well, then keep some
vector<int> previousand each time when updating distance of vertex (sayv) setprevious[v] = index of vertex from where you came here. Your path islast, prev[last], prev[prev[last]],...,firstin reversed order.