c++ - 如何将图的一部分压缩成单个节点并能够找到从一个节点到所有节点的最短路径？

Question

我有一个具有以下特征的图 -

1. 共有 N 个节点 (1,2...N)。
2. 所有边都是双向。
3. 从 1 到 K(K <=N )的节点以相同的权重 W 相互连接。
4. 并且有M条边。这 M 条边可能具有不同的权重。此外，这些 M 边可以在任何节点到任何其他节点之间(可以在 N-K 个节点之间或从前 K 个节点到其他 N-K 个节点。
5. 肯定存在从一个节点到达另一个节点的路径。

An example graph having these features.

我需要找到从给定节点到所有其他节点的最短路径距离。

现在我在想，与其直接使用 Dijkstra 算法来寻找从给定节点到所有其他节点的最短路径，不如将节点 1 的子图压缩为更优化 K 到单个节点中，因为它只需要 O(1) 时间就可以找到从任何 K 个节点到任何其他 K 个节点的距离，因为它固定为值 W 并且每个K 个节点中的一个相互连接。

但我想不出如何编写代码或修改我的 Dijkstra 算法。我想知道如何着手解决这个问题，如果可能的话还有更好的解决方案吗？

Answer 1

让我们使用一个标准的 Dijkstra 算法并稍加改动:我们将保留一个支持三种操作的线段树:

1. 获取范围内的最小值
2. 将给定位置的值设置为+INF
3. 进行范围更新(为所有 a[i] = min(a[i], new_val) 设置 l <= i <= r)

标准线段树可以处理 O(log N) 中的所有这些操作时间。

我们可以照顾所有“其他” M以标准方式连接边(我们获取子节点的值，更新它并在必要时将其放回树中)。

第一个 K 之间的边节点可以这样处理:如果当前节点v是第一个K ，我们对 [1, K] 进行范围更新值为 dist[v] + W 的段.

就是这样。最多有 K <= N第二种类型的更新和M第一次更新(就像在标准的 Dijkstra 算法中一样)。所以总的时间复杂度是O((M + N) log N) ，无论多大K是。