C++ - 我应该为 Dijkstra 使用什么数据结构？
C++ - what data structures for Dijkstra's should I use?
任务是：
找到两个城市之间的最短路径。城市与单行道相连。
城市以这种方式存在于 .txt 文件中：
// From // // To // // Distance //
例如：
London Glasgow 180
Manchester Liverpool 80
York Cambridge 415
York Manchester 260
Glasgow York 315
Glasgow Manchester 315
给定源城市 S 和目标城市 T，求最短路径。计算距离并检索所走的路径。
问题是：我根本不允许使用任何STL容器。不能使用 std::list、std::vector、std::pair、std::set 等容器。但是，我可以使用自己实现的动态数据结构。
我不知道应该实现哪些数据结构以及如何实现它们。
另外，我应该使用优先级队列、堆还是其他东西？
还想知道邻接表或邻接矩阵。
我真的不在乎解决方案是否经过优化。
我一直在谷歌搜索，但我发现所有 Dijkstras 算法实现都使用了大量的 STL 容器，我不允许使用这些容器。
感谢任何提示、提示或链接。谢谢。
要编写 Dijkstra 的最短路径算法，您只需实现一个优先级队列（最小堆）。
我首先推荐堆。集合的实现涉及（几乎）平衡二叉搜索树，如 AVL 或 Red-Black Tree 或 Treap（笛卡尔树），此类代码比实现堆要难几个数量级。此外，所有这些解决方案都具有相同的 运行 时间 O(log n)，因此更容易编写解决方案。
任务是：
找到两个城市之间的最短路径。城市与单行道相连。 城市以这种方式存在于 .txt 文件中：
// From // // To // // Distance //
例如：
London Glasgow 180
Manchester Liverpool 80
York Cambridge 415
York Manchester 260
Glasgow York 315
Glasgow Manchester 315
给定源城市 S 和目标城市 T，求最短路径。计算距离并检索所走的路径。
问题是：我根本不允许使用任何STL容器。不能使用 std::list、std::vector、std::pair、std::set 等容器。但是，我可以使用自己实现的动态数据结构。
我不知道应该实现哪些数据结构以及如何实现它们。 另外，我应该使用优先级队列、堆还是其他东西？ 还想知道邻接表或邻接矩阵。
我真的不在乎解决方案是否经过优化。
我一直在谷歌搜索，但我发现所有 Dijkstras 算法实现都使用了大量的 STL 容器，我不允许使用这些容器。
感谢任何提示、提示或链接。谢谢。
要编写 Dijkstra 的最短路径算法，您只需实现一个优先级队列（最小堆）。
我首先推荐堆。集合的实现涉及（几乎）平衡二叉搜索树，如 AVL 或 Red-Black Tree 或 Treap（笛卡尔树），此类代码比实现堆要难几个数量级。此外，所有这些解决方案都具有相同的 运行 时间 O(log n)，因此更容易编写解决方案。