c++ - dijkstra 的算法 - 在 C++ 中？

Question

在过去的四天里，我试图了解 dijkstra 的算法。但我不能。我有一个点 vector 。由此我创建了一个成本矩阵。但我不知道如何制作dijkstra的算法。资源可在网上获得，但我不是计算机科学背景，所以我无法理解它们。我正在尝试制作这样的功能

vector<int> dijkstra(costMatrix[][])
{
  ....
  ....
  return vector<int>pathPointindex
}

main()
{
    vector<Point> availablePoints;
    costMatrix[][]=createCostMatrix();
    vector<int> indexes=dijikstra(costMatrix)
    for(int i=0;i<indexes.size();i++)
       cout << "path points are " << availablePoints[indexes[i]] << endl;
}

如果有人，请您发布代码。我并不懒惰。但是我的项目在一天前就已经超过了截止日期。现在我失去了理解逻辑的希望。现在只是我想要的功能。 “有需要的人真是天使”。

编辑:特别感谢“Loki astari”的出色回答

Answer 1

Dijkstra 算法

用英语讲:

这是一种寻找从 A 点到 B 点的最短路径的算法。
在计算方面，我们将路径简化为由节点和弧组成的图。每个节点代表一个中间点，而每条弧线连接两个节点，并具有一个(非负)权重，表示在两个节点之间遍历的成本。

要实现该算法，您需要两个列表:

• 完成:一组(节点，成本)，您已计算出要达到的最低成本。
• working:已检查的(节点、成本)的排序列表。

算法:

working.addNode(Start, 0); // No cost to get to start.

for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
    // If we have already processed this node ignore it.
    if (finished.find(node))
    {    continue;
    }

    // We have just removed a node from working.
    // Because it is the top of the list it is guaranteed to be the shortest route to
    // the node. If there is another route to the node it must go through one of the
    // other nodes in the working list which means the cost to reach it will be higher
    // (because working is sorted). Thus we have found the shortest route to the node.

    // As we have found the shortest route to the node save it in finished.
    finished.addNode(node,cost);

    // For each arc leading from this node we need to find where we can get to.
    foreach(arc in node.arcs())
    {
        dest = arc.dest();
        if (NOT (finished.find(dest)))
        {
            // If the node is already in finished then we don't need to worry about it
            // as that will be the shortest route other wise calculate the cost and add
            // this new node to the working list.
            destCost = arc.cost() + cost;
            working.addNode(dest,destCost); // Note. Working is sorted list
        }
    }
} 

所以如果你考虑一下这个算法。假设您要从伦敦前往曼彻斯特。

finished = {} // empty.
working  = { (London,0) }

使用以下成本矩阵:

                  L    S    O    B    N    M    W
(L) ondon         -    50   60   100  130  -    -
(S) outhampton    50   -    70   -    -    -    -
(O) xford         60   70   -    50   -    200  -
(B) irmingham     100  -    50   -    -    80   110
(N) orwich        130  -    -    -    -    -    -
(M) anchester     -    -    200  80   -    -    80
Ne(W) castle      -    -    -    110  -    80   -

现在您将伦敦从工作列表中取出(因为它位于首位)并将其放入完成列表中。然后将与伦敦直接相连的所有城镇添加到工作列表中。

finished = { (London,0) }
working  = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }

考虑工作场景中的城镇是从伦敦扩展的泡沫的外缘。 Dijkstra 算法的工作是不断扩大泡沫，直到我们到达曼彻斯特(不追溯我们已经采取的任何步骤)。所以气泡总是向外膨胀，我们总是把气泡中最小的部分膨胀。

所以下一步是占据列表的头部并重复。从南安普敦出发，只有两个目的地。回到伦敦(我们将其丢弃在完成的列表中)和牛津。到牛津的费用是 50 + 从南安普顿到牛津的费用(所以请注意它两次在工作列表中，但不要担心我们会因为不是最佳路线而放弃它)。

finished = { (London,0), (Southampton,50) }
working  = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }

所以重复循环。榜首是牛津。从牛津出发，我们可以去曼彻斯特(200)、伯明翰(50)或返回伦敦(60)或南安普顿(请记住，我们需要将到达牛津的费用加到上面的每一项费用中。请注意，从牛津出发，我们可以去了南安普敦，但我们已经找到了到南安普敦的最短路线，因此不需要处理)这将为我们留下:

finished = { (London,0), (Southampton,50), (Oxford, 60) }
working  = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}

请注意，我们现在将曼彻斯特列入工作列表(这是我们的目的地)。但是我们需要继续努力，因为我们可能会找到一条更短的路线。所以现在我们从伯明翰扩展。从那里我们可以去牛津(50)，曼彻斯特(80)，伦敦(100)，纽卡斯尔(110)。首先加上去伯明翰的费用，这给了我们:

finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working  = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}

接下来的两个节点。牛津和伯明翰已经在完成列表中，所以我们可以忽略它们。因此，除非从诺里奇到曼彻斯特的路线少于 50 英里，否则我们将在之后的迭代中到达曼彻斯特。