实现Dijkstra算法

下面是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)。

通向的道路 X 通过 V 比当前最短路径长 X 所以我们忽略了它。然而,通往 Y 和 Z 经过 V 比以前已知的最短路径短,因此我们更新它们。

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

如果你从未写过类似的东西,那么在C++中实现DijkStA算法是一个相当激烈的问题。在阅读了维基百科的页面之后,这里有一些让你开始的想法。

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 (不是我们稍后将看到的优先级队列)。为此创建一个单独的向量,因为我们需要从中添加和删除内容。查找如何提供将顶点放在最低的谓词 dist_from_source 在堆的顶部。

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

这就是为什么我们不使用 priority_queue 对于 Q . 你需要知道 v 仍然在 Q . 优先队列不允许您这样做。

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

现在你需要的是距离函数 图 . 你没有说图形数据是如何定义的,所以你在这里有点独立自主。

17      return dist[]

这一行只意味着返回产生最短路径所需的任何数据。基本上是所有顶点的集合 prev 和 与源的距离 填满。

首先需要的是一种表示图形的方法。通常这是 vertex 对象,每个对象都包含一个相邻列表。在C++中,这可以是指向其他顶点的指针列表。确保顶点不可分割。例如,您可以给每个人一个唯一的ID号。

那么,维基百科上的代码应该更有意义。每次你有伪代码的时候 dist[v] ,您要使用 map<VertexIdNumber, double> .

这个 Wikipedia article link 我把它塞进操作系统中,给出了一个非常清晰和简洁的描述,以及动画图形。

可能丢失的键(?)在算法的每个步骤中,您都可能更新到连接到“当前”节点的每个节点的最短路径。对于四节点的“菱形”情况,如果a是起点,d是终点,首先计算到b和c的距离,然后从b计算到a到d的距离,然后也计算到c。如果通过c的路径较短,则“从a到d的最短路径”是通过c。如果通过c的路径较长,则最短路径是通过b。这应该很明显(?)扩展到更复杂的网络。

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

我遇到的一个小问题是存储次优的半成形路径,以防它们变得最佳。当我访问一个给定的节点时,我只是不知道如何更新通过它的所有连接。

我想你可能对算法有点误解。Dijkstra的工作原理是按照距离的增加顺序来探索节点;因此,您可以保证找到到任何永久标记的节点的最小距离和最佳路径。

在运行算法时,通常不会显式存储任何路径。相反,考虑您正在图上构建一个生成树——所以只有一种方法可以到达树上的每个节点。您只需要针对每个节点存储一个距离标签及其父节点。当你在搜索过程中第一次看到每个节点时,你会暂时地给它贴上标签;很可能以后你会找到一条更好的路径——但是在那一点上你需要更新的只是单个节点的距离和父标签。

一旦你永久地标记了你的目的地,你就可以停下来,然后你可以通过向上移动父标签回到源位置来获得到达目的地的最佳路线。

希望有帮助:)

这个回答对你来说可能太晚了,但我会提供它,以防它对其他人有帮助。

首先,你需要澄清

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

我在大学里学过这类算法已经25年了,但从记忆中可以看出,Warshall算法更容易用矩阵法实现。你可以看看这里: www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf] .