通过节点子集中至少 1 个节点的最短路径

Question

我想实现一个 python 函数，该函数在有向加权图中生成从源节点到目标节点的最短路径。它必须包括图中节点子集中的至少一个节点，并且路径必须是该子集中的最短路径。你如何在 O(ElogV) 时间内实现这一点，其中 E 和 V 是边和节点的数量？

Answer 1

运行 Djikstra 来自源节点。然后，反转图中的所有边。在这个新图上，运行 Djikstra 来自目标节点。到源节点（原图中）的距离和到目的节点（反转图中）的距离之和最小的节点是最短路径经过的节点。一旦确定了这个节点，就可以读出最短路径中的实际节点。

Djikstra 花了 O(E log V) 时间，我们 运行 花了两次。找到总和最小的节点需要 O(V) 时间，而读取答案需要 O(E) 时间。所以，这个算法的运行时间是O(E log V).

---

_{根据 these recommendations，此答案故意不完整。如果几天后您仍然遇到困难，post 发表评论，我可以提供进一步的建议。}