1

给定一个无向加权图，两个节点之间的长度是整数。

如何打印图中距离最小的节点对。如果有多对，打印所有

4

1 回答 1

2

让我们同意，我们正在无向加权图 G 上寻找简单的路径（没有重复的顶点）。

两个顶点u和v之间的最小距离路径的数量可以达到 (n-2)！（具有零权重边的完整图，从u开始到v结束的每个排列都是有效的最小距离路径）。

尽管如此，如果您设法创建一个具有与 G 相同顶点的新图 G' 并且其边属于u和v在 G 中。

构建 G' 的简单方法是：

  1. 计算从u开始并保持距离数组 (du)的单源最短路径。
  2. 计算从v开始并保持距离数组 (dv)的单源最短路径。
  3. 使用 G 中的所有节点和零边创建 G'。
  4. 对于G 中的每条边 < x , y >（< x , y > 的权重为w），如果 du[x] + w + dv[y] == du[v] 或 du[y] + w + dv[ x] == du[v] 则 <x, y> 属于 G'。

如果在第 4 步强制边缘方向并且没有零权重循环，则 G' 是 DAG（有向无环图）。您可以使用 DAG 属性计算 G' 中u和v之间的最小距离路径量，并作为 sidequest 证明这样的答案等于原始问题的答案。此外，如果在找到v时从u回溯，那么您将获得G 中u和v之间的最小距离路径。

您可以使用 dijkstra 算法或 Bellman-Ford 算法根据您的权重约束计算单源最短路径。

于 2020-09-21T21:59:50.150 回答