c++ - 用 C++ 编写 Dijkstra 算法

Question

我有一个作业，给我一张图，必须使用二维数组并找到从“Macomb”到“Chicago”的最短路径。我很难弄清楚我应该如何开始。

看了几个视频，觉得自己对Dijkstra算法的原理有所了解，但是转成代码就比较吃力了。

我为我的图创建了一个邻接矩阵，其中我使用“99”来表示不存在的边，我为前辈列表创建了一个数组，为剩余的顶点创建了一个数组。我应该将每个新的添加输出到最佳路径，以及每个添加到最佳路径的当前成本。最后，它应该是这样的:

路径:马科姆
费用:0
路径:马科姆 --> 希望
成本:2
路径:马科姆 --> 希望 --> 爱
成本:4
路径:马科姆 --> 希望 --> 爱 --> 和平
花费:5
路径:马科姆 --> 希望 --> 爱 --> 和平 --> 信仰
费用:6
路径:马科姆 --> 希望 --> 爱 --> 和平 --> 信仰 --> 芝加哥
费用:8

这是我必须开始的代码:

#include <iostream>

using namespace std;



int main()
{
int graph[6][6] = {{99,2,9,5,99,99},
                   {2,99,4,2,99,99},
                   {9,4,99,1,1,5},
                   {5,2,1,99,4,99},
                  {99,99,1,4,99,2},
                  {99,99,99,99,2,99}};
string pred[6] = {"Macomb", " ", " ", " ", " ", " "};
string cities[5] = {"hope", "peace", "love", "belief", "Chicago"};
int distance[6];

}

我不是在找人帮我写作业，但我很感激任何朝着正确方向前进的人，因为这是一项艰巨的任务。这是针对基本数据结构类的，我们唯一使用的 #include 是代码中的内容，因此答案越不复杂越好。

谢谢!

Answer 1

这是我对 Dijkstra 算法的实现。

https://github.com/Jesusfer2575/Reference/blob/master/dijkstra.cpp

好好享受吧!