logo标签列表

实现Dijkstra算法

c++dijkstra
5
我被分配（大学课程作业）实现一种路径查找。现在，在规范中，我可以只实现蛮力算法，因为有一个限制要搜索的节点数量（起点，两个中间点，终点），但我想重复使用这段代码并来实现Dijkstra's algorithm。
我已经在维基百科上看到了伪代码，我的一个朋友也写了一些代码给我，但它根本就不可理解。该算法似乎非常简单，我没有问题理解它，但是我就是无法想象出能够实现这种算法的代码。
有什么建议或提示吗？

针对一些混淆的问题进行编辑：
是的，有目标节点和源节点。
我想要实现Dijkstra算法的一般情况，而不是“只有两个中间站”的情况，因为我之后想要再次使用这段代码。否则，我会写一个暴力实现。
我遇到的具体问题是存储半成品子路径，以防它们变得更优。当我访问给定节点时，我不知道如何更新通过它的所有连接。
更多编辑：
现在正在查看一些答案并尝试解决问题。

真正的编辑： 我忘记提到一个严重的复杂性，即任意两个顶点之间可以有最多UINT_MAX个不同的距离。抱歉。事实上，我忘记处理这个问题可能是问题的根本原因，尽管解决方案：选择最短距离对我来说很明显。难怪其他人的伪距离变量没有考虑我的距离变量。

1
标记为作业，因为OP明确提到了课程作业。 - Aryabhatta
你到底卡在哪里了？是从伪代码转成实际代码吗？还是理解伪代码和算法之间的联系？ - Cascabel
5
你无法将直接打印在维基百科文章中的伪代码进行可视化吗？ - Billy ONeal
我能看到它，但它没有意义。我也不能用C++自己编写。白痴：如果你重新阅读，你会发现我可以使用暴力方法。所以这不是一个作业问题，因为对于我的作业，我可以实现几乎任何东西并称其为成功。 - Puppy
1
（我添加了WP链接，请勿在OP上放置） :) - dash-tom-bang
6个回答
8
这里是Dijkstra算法的高级概述：
将所有顶点放入一个优先队列中，其中所有顶点的优先级（距离）均为无穷大，除了源顶点，其距离为零（源顶点与自身的距离为零，对吧？）。
弹出优先队列。被移除的顶点是距离源最近的顶点。显然，从队列中弹出的第一个顶点就是源顶点。我们称这个弹出的顶点为v。
查看v的每个邻居。它们中的所有顶点的距离都大于v的距离（否则我们已经从队列中弹出它们了，对吧？）。假设v的距离为3，v有3个邻居x（距离源：5）、y（距离源：10）和z（距离源：无穷大）。
现在我们看一下每个邻居到v的距离。假设它们分别为：x-3、y-2、z-4。这意味着从源到x的路径通过v的距离为|v|+3（3+3=6），y的距离为5（3+2=5），z的距离为7（3+4=7）。
通过v到达x的路径比当前已知的最短路径更长，因此我们忽略它。但是通过v到达y和z的路径比以前已知的最短路径更短，因此我们更新它们。
您一直这样做，直到遍历完所有顶点。在每个点上，当您从优先队列中弹出最小值时，您就知道您已经找到了到该顶点的最短路径，因为任何可能更短的路径都必须经过距离小于v的顶点，这意味着我们已经从队列中弹出了那个顶点。
1
也许不是很明显，但你不需要遍历所有的顶点。你只需在弹出目标顶点之前，遍历到所有的顶点。可能仍然存在着在队列中距离源顶点比目标顶点更远的顶点，但这些顶点并不重要，因为显然不会有更短的路径通过它们！ - dash-tom-bang
DeadMG 没有说他有一个目标，因此我假设他想要所有顶点的最短路径。如果他正在寻找从源到目标的最短路径，那么你是正确的，尽管在这种情况下我会推荐使用A*算法。 - Niki Yoshiuchi
1
Niki，DeadMG说有四个节点：“开始，中间两个，结束。”我认为可以安全地假设目标是从开始到结束的最短路径，因此目标是结束。 - Rob Kennedy
2
对于OP的特定情况来说，这并不重要，因为只有四个节点，但如果他想要一个通用的可重复使用的算法，将所有顶点一开始都放入优先队列中是不可扩展的。无论如何，这没有太大意义，因为在弹出它们之前，你会更新它们 - 所以最好在第一次到达时插入它们。 - Peter
3

如果你从未编写过 Dijkstra 算法相关的代码，那么在 C++ 中实现它是一项相当复杂的任务。通过阅读维基百科页面，以下是一些启示，可以帮助你开始编写。

struct Vertex {
    int id;
    std::vector<int> neighbors;
    int dist_from_source;  // need some sentry value for "infinity"
    int prev;  // need some sentry value for "undefined"
};

这是基于几行伪代码的。一个图(Graph)可以是std::vector<Vertex>，并且还需要一些方法来确定两个顶点之间的距离。
8     u := vertex in Q with smallest dist[]

这一行表示需要使用 std::make_heap（而不是稍后会介绍的priority_queue）。为此，需要单独创建一个向量，因为我们需要从中添加和删除元素。查找如何提供一个谓词，使距离源节点最近的顶点位于堆的顶部。

12      for each neighbor v of u: // where v has not yet been removed from Q.

以下是我们不使用priority_queue来处理Q的原因。你需要确定v是否仍在Q中，而priority_queue无法实现这一点。

13        alt := dist[u] + dist_between(u, v)

现在你需要使用Graph提供的距离函数。由于你没有说明图形数据是如何定义的，所以这里有点棘手。

17      return dist[]

这行代码的意思是返回产生最短路径所需的所有数据。基本上，这是一组顶点，其中每个顶点都填充了prev和dist_from_source。

1

我在原帖中放置的维基百科文章链接提供了非常清晰简洁的描述，还有动画图形。

可能缺失的关键是，在算法的每个步骤中，您可能会更新与“当前”节点相连的每个节点的最短路径。对于您的四节点“钻石”案例，如果A是起点，D是终点，则首先计算到B和C的距离，然后从B计算从A到D的距离，然后也通过C进行计算。如果通过C的路径更短，则“从A到D的最短路径”是通过C。如果通过C的路径更长，则最短路径经过B。这显然可以扩展到更复杂的网络。

关于原帖的真正编辑：两个节点之间有多少连接并不重要。实际上，这就是算法的重点，检查所有可能路径上的所有连接。如果节点A和节点B由两条道路连接，并且您想要最短的道路，请不要担心较长的道路，只需将其丢弃即可。始终尝试丢弃您知道与问题无关的数据。

1

你需要的第一件事是一种表示图形的方法。通常这是一个包含邻接表的vertex对象的集合。在C++中，这可以是指向其他顶点的指针列表。确保顶点具有可比较性（LessThanComparable）。例如，您可以为每个顶点分配唯一的ID号码。

然后，维基百科上的代码应该更容易理解。每次您使用类似于dist[v]的伪代码时，都要使用map<VertexIdNumber, double>。

0
我遇到的具体问题是存储次优路径，以防它们可能成为最优解。当我访问一个给定节点时，我不知道如何更新通过它的所有连接。
我认为您可能有点误解算法。Dijkstra算法按照距离递增的顺序探索节点；因此，您可以确保已找到任何永久标记节点的最小距离和最优路径。
在运行算法时，您通常不会显式存储任何路径。相反，考虑在图上构建生成树 - 因此只有一种方法可以到达该树上的每个节点。您只需要针对每个节点存储一个距离标签和其父节点即可。在搜索期间首次看到每个节点时，您将暂时标记它；以后可能会找到更好的路线，但在那时，您只需更新单个节点的距离和父标签即可。
一旦您永久标记了目的地，就可以停止搜索，然后通过向上沿着父标签走回源获取到最优路线。
希望能帮到您 :)
-2

这个回复可能对你来说有点晚了，但我提供它以帮助其他人。

首先，您需要澄清以下问题：

  1. 节点之间的边是否具有不同的权重
  2. 图是有向还是无向的

距我在大学学习这些算法已经有25年了，但从记忆中，沃沙尔算法更容易通过矩阵方法实现。您可以在这里查看：www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf]。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接