我实现了一个函数，该函数使用 Dijkstra 的算法在加权、无向图(正权重(中找到从给定源节点到任何给定目标节点的最短(最低权重(路径。
我有两个列表 A 和 B，每个列表至少包含一个节点位置，并且它们持有的每个节点都是有效的(在图中(。列表 A 中的节点也可以位于列表 B 中，反之亦然。
我需要扩展我的函数，以便它也将列表 A 和 B 作为输入，并找到从源节点到目标节点的最短路径，该路径至少使用 A 和 B 中的一个节点。此外，虽然它可以在路径中的任何点使用 A 和 B 节点，但它必须在使用 A 节点(或使用同时位于 A 和 B 中的节点(后使用 B 节点。
如果节点同时位于 A 和 B 中，则立即满足此要求。
源节点和目标节点都可以位于 A 和/或 B 中。
例如
有效路径(S 是源，D 是目标，N 是不在 A 或 B 中的节点(：
- S> A> B> D S> B>
- A> B> D S> N> B>
- A> N> B> D
- S> (A&B(> D
- S(A(> D(B(
无效路径：
- S> B> A> D
我如何能够扩展它，使其保持Dijkstra算法O(Elog(V((的复杂性？E 是边的 #，顶点的 V #。我认为一定有一种方法可以使用Dijkstra的算法恒定次数来做到这一点，因此复杂性不会改变。为任何帮助干杯。
我建议通过跟踪每个节点另外两个值来扩展Dijkstra。访问 A 的最短路径和访问 A>B 的最短路径(A 然后是 B(。
通常，您会跟踪到Dijkstra中每个节点的最短路径。现在，您将跟踪三个最短路径。您仍将处理单个步骤并将新邻居添加到队列中，但这一次，有三种可能性：
-
未访问 A 的到达节点：对于不在 A 中的所有邻居，更新暂定的">无 A"距离。对于 A 中的所有邻居，更新暂定的">与 A"距离。对于 A 和 B 中的所有相邻要素，更新暂定的">A>B"距离。
-
到达节点访问 A 但之后没有访问B：对于不在 B 中的所有邻居，更新暂定">与 A"距离。对于 B 中的所有邻居，更新暂定的">A>B"距离。
- 到达节点访问 A，然后访问 B如果最终节点，则找到结果。否则，更新所有邻居暂定">A>B"距离。
始终选择具有最小暂定距离的节点，就像在原始算法中一样。为此，您到达节点的条件并不重要。