algorithm - Dijkstra 最短路径算法

Question

CLRS 中的 Dijkstra 算法，p.595 在第 7 行中有以下代码:

for each vertex v \in Adj[u]

这一行选择迭代节点 v 的所有邻居。这里的节点 v 是算法当前正在处理并添加到最短路径树的节点。
然而，在 v 的那些邻居中，已经在集合 S 中的那些被处理并完成，而那些
S 中的节点正在形成最短路径树 T。
集合 S 中的任何节点都不能具有比 T 中已有的路径更短的路径直通 v。
否则，那条路就会一直走到那个时候。

所以，第 7 行不应该更好吗

for each vertex v \in Adj[u] \intersect Q   // Q = V \ S

或者，同样地，

for each vertex v \in Adj[u]\S 

?

//============================

添加说明:

一旦你处理(处理=设置距离和父向量
其所有直接邻居的条目)一个节点 u 并将其添加到树中，
该节点 u 与源的距离最短。如果有一个树外节点
z 以便在源和 u 之间存在一条到 u 的较短路径，该节点 z 将在 u 之前处理。

//======================

附加 2:对下面哈维尔有用答案的冗长评论:

将图中的所有边放在一个数组中，比如“EDGES”——一条边，一个数组条目。
每个数组条目保存边 (u,v)、边权重和 2 个指针——一个指向节点 u，一个指向节点 v。

该图仍然表示为邻接表。

Adj[u] 仍然是一个链表——然而，这个链表是在一个数组结构上。
这次列表中的节点值是与该边对应的 EDGES 的索引。

因此，例如，节点 u 有 2 个关联到它的链接:
(u,x) & (u,y)。 Edge (u,x) 位于 EDGES 的第 23 个单元格，(u,y) 位于第 5 个单元格。
那么，Adj[u] 是一个长度为 2 的链表，这个链表中的节点是 23 和 5。比如说 Adj[u][0].edgesIndex=23 和 Adj[u][1].edgesIndex=5。这里， Adj[x][i].edgesIndex=23 对于 Adj[x] 的链表中的某些 i。 (Adj[j][i]，作为链表中的一个节点，在其上进一步具有“next”和“prev”字段。)

并且，EDGES[23] 有一个指向 Adj[u] 上的 (u,x) 的对应条目，另一个指向 Adj[x] 的条目。我保留第 7 行，但这次，在我处理该循环中的边 (u,v) 之后，(我从 Adj[u] 中发现了这条边)，我从Adj[u]，从那里我转到相应的 EDGES 条目，该条目引用了相应的 Adj[x][i] 条目。我将它们全部删除——EDGES[23]、Adj[u][0] 和 Adj[x][i](无论我在那里。)对于所有数组结构，我可以在恒定时间内为每个边处理所有这些.

仍然是邻接列表表示，可以从 (u,v) 跟踪 (v,u) 的位置并在恒定时间将它们删除，现在仅在该交叉点的边缘上进行处理，我正在寻找渐近相同数量的使用的内存和更多的时间效率。

//====================

补充 3:

更正上面 ADDITION 2 中的一件事:

我在那个添加中写的内容可能需要更多——不少于没有它的算法的时间:

删除链表中 Adj[u] 和 Adj[x] 处的链接，以及相应的
EDGES 条目，所有这些期间的直接内存查找不太可能
与在算法中放松边缘相比，占用更少的 CPU 周期。

它仍然只检查每条边 (u,v) 一次而不是两次——
一次用于 (u,v) 一次用于 (v,u)，并且显然与没有它的算法在相同的渐近时间内。但对于绝对 yield 微乎其微
处理时间和使用的内存成本更高。

另一种选择是:
添加一行类似的东西

if (v \in S) then continue; 

作为 for 循环的第一个。这可以通过将 S 保持为
bool 数组 S[|V|] 并相应地设置其值，因为每个顶点是
添加到设置 S - 这基本上是哈维尔在他的回答中所说的。

Answer 1

相交Adj[u]与 Q是正确的，但这不是一个好主意，因为最后，您需要遍历 Adj[i] 的所有元素.我认为没有办法解决这个问题。

只有当你能找到一种非常有效地将这两个集合相交的方法时，它才会起作用，即任何比 O(n) 更好的方法。

您实现的一个很好的增强是标记所有已解决的节点，然后如果节点 v已解决，您可以忽略内部循环的其余部分。