5

我的任务是（课程@大学）实施一种寻路形式。现在，在规范中，我可以只实施蛮力，因为要搜索的节点数量有限制（开始，中间两个，结束），但我想重用这段代码并来实现Dijkstra 的算法。

我在 Wikipedia 上看到了伪，一个朋友也为我写了一些，但这完全没有意义。该算法看起来很简单，理解它对我来说不是问题，但我无法终生想象实现这种事情的代码。

有什么建议/提示吗？

编辑一些混淆：
是的，有一个目标节点和一个源节点。
我希望在一般情况下实现 Dijkstra，而不是“只有两个中间停止”的情况，因为我想在之后再次使用该代码。否则，我只会写一个蛮力实现。
我遇到一点麻烦的具体问题是存储次优的半形成路径，以防它们变得最优。当我访问给定节点时，我只是看不到如何更新通过它的所有连接。
更多编辑：
现在通过几个答案并试一试。

真正的编辑：我忘了提到一个严重的并发症，即任何两个顶点之间最多可以有 UINT_MAX 不同的距离。对不起。事实上，我忘记处理这个事实可能首先是导致该死问题的原因，尽管解决方案：选择最短的对我来说是幸运的。难怪其他人对距离变量的伪没有考虑到我的变量距离。

4

6 回答 6

8

这是 Dijkstra 算法的高级分解：

您将所有顶点粘贴在优先级队列中，其中所有顶点的优先级（距离）为无穷大，但源顶点的距离为零（源顶点距自身的距离为零，对吧？ ）。

弹出优先队列。移除的顶点是距离源最短的顶点。显然，从队列中弹出的第一个顶点就是源。好吧，称之为弹出的顶点v。

查看v的每个邻居。它们的距离都将大于v的距离（否则我们已经将它们从队列中弹出，对吧？）。假设v的距离为 3，v有 3 个邻居x (dist-from-source: 5)、y (dist-from-source: 10) 和z (dist-from-source: infinity)。

现在我们看看每个邻居与v的距离。假设它们是：x - 3, y - 2, z - 4。这意味着从源到x的路径经过v的距离为 | v | + 3 (3 + 3 = 6)，y的距离为 5 (3 + 2 = 5)，z 的距离为 7 (3 + 4 = 7)。

到x到v的路径比当前到x的最短路径长，所以我们忽略它。然而，通过v到y和z的路径比之前已知的最短路径短，因此我们更新它们。

你一直这样做，直到你穿过所有的顶点。在每一点，当您从优先级队列中弹出 min 时，您知道您已经找到了到该顶点的最短路径，因为任何可能的较短路径都必须通过距离小于v的顶点，这意味着我们已经弹出从队列中。

于 2010-05-24T18:35:08.873 回答
3

如果您从未编写过类似的东西，那么在 C++ 中实现 Dijksta 算法是一个非常棘手的问题。阅读 Wikipedia 页面后，这里有一些想法可以帮助您入门。

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"
};

这是基于前几行伪代码。AGraph可以通过std::vector<Vertex>某种方式来识别两个顶点之间的距离。

8     u := vertex in Q with smallest dist[]

该行表示需要std::make_heap（不是我们稍后会看到的 priority_queue）。为此创建一个单独的向量，因为我们需要从中添加和删除东西。查找如何提供一个谓词，将最低的 Vertexdist_from_source放在堆的顶部。

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

这就是我们不使用priority_queuefor的原因Q。您需要确定是否v仍在Q. priority_queue 不允许您这样做。

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

现在你需要附带的距离函数Graph。你没有说图形数据是如何定义的，所以你在这里有点自己。

17      return dist[]

此行仅表示返回生成最短路径所需的任何数据。它基本上是一组顶点，所有顶点都有prev并dist_from_source填充。

于 2010-05-24T19:41:48.933 回答
1

您需要的第一件事是一种表示图形的方法。通常这是一组vertex对象，每个对象都包含一个邻接列表。在 c++ 中，这可能是指向其他顶点的指针列表。确保顶点是 LessThanComparable。例如，您可以给每个人一个唯一的 ID 号。

然后，维基百科上的代码应该更有意义。每次你有类似的伪代码时dist[v]，你都想使用map<VertexIdNumber, double>.

于 2010-05-24T18:28:33.547 回答
1

我塞进 OP的Wikipedia 文章链接提供了非常清晰简洁的描述，以及动画图形。

可能缺少的关键（？）是，在算法的每个步骤中，您可能会更新连接到“当前”节点的每个节点的最短路径。对于您的四节点“菱形”情况，如果 A 是起点，D 是终点，首先计算到 B 和 C 的距离，然后从 B 计算从 A 到 D 的距离，然后也通过 C 进行计算。如果通过 C 的路径更短，那么“从 A 到 D 的最短路径”是通过 C。如果通过 C 的路径更长，那么最短路径通过 B。这显然应该（？）扩展到更复杂的网络。

在 OP 的真正编辑上：两个节点之间有多少连接并不重要。事实上，这就是算法的重点，检查所有可能路径的所有连接。如果节点 A 和节点 B 由两条路相连，而你想要最短的路，不要担心路更长，直接扔掉。始终尝试丢弃您知道与您的问题无关的数据。

于 2010-05-24T18:28:18.670 回答
0

我遇到一点麻烦的具体问题是存储次优的半形成路径，以防它们变得最优。当我访问给定节点时，我只是看不到如何更新通过它的所有连接。

我想也许你对算法有点误解。Dijkstra 通过按距离递增的顺序探索节点来工作；因此，您可以保证找到到任何已永久标记的节点的最小距离和最佳路径。

运行算法时，您通常不会显式存储任何路径。相反，请考虑您正在图形上构建生成树 - 因此只有一种方法可以到达该树上的每个节点。您需要针对每个节点存储的只是距离标签及其父节点。当你在搜索过程中第一次看到每个节点时，你会暂时标记它；稍后您可能会找到更好的路线 - 但此时您必须更新的是该单个节点的距离和父标签。

永久标记目的地后，您可以停下来，然后您可以通过将父标签向上走回源来获得到达目的地的最佳路线。

希望有帮助:)

于 2010-05-24T23:00:28.270 回答
-2

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

首先你需要明确是否

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

我在大学学习此类算法已有 25 年了，但从记忆中 Warshall 算法更容易通过矩阵方法实现。你可能会看这里：www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf]。

于 2010-06-05T00:33:45.917 回答