打印无向加权图中2个节点之间的所有最小路径
Print all minimum paths between 2 nodes in an undirected weighted graph
给定一个无向加权图，2个节点之间的长度是整数。
如何打印图中具有最小距离的对节点。如果有多对，则全部打印出来
假设我们正在无向加权图 G 上寻找简单路径（无重复顶点）。
两个顶点u和v之间的最小距离路径数量最多可达(n-2)条！ （具有零权重边的完整图，从 u 开始并在 v 结束的每个排列都是有效的最小距离路径）。
尽管如此，如果您设法创建一个新图 G'，它具有与 G 相同的顶点并且其边属于某个最小值，则您可以计算出此类路径的数量或回溯以找到每条路径G.
中 u 和 v 之间的距离路径
构建 G' 的简单方法是：
- 计算从u开始的单源最短路径并保持距离数组(du)。
- 计算从 v 开始的单源最短路径并保持距离数组 (dv)。
- 使用来自 G 的所有节点和零条边创建 G'。
- 对于 G 中的每条边 <x、y>（<x 的权重, y> 是 w), 如果 du[x] + w + dv[y] == du[v] 或 du[y] + w + dv[x] == du[v] 那么
属于 G'.
如果您在第 4 步强制边缘方向并且没有零权重循环，则 G' 是 DAG（有向无环图）。您可以使用 DAG 属性 来计算 G' 中 u 和 v 之间的最小距离路径的数量，并且作为 sidequest 证明这样的答案是等于原问题的答案。此外，如果从 u 回溯，只要它找到 v 那么你就会获得 u 和之间的最小距离路径v 中 G.
您可以使用dijkstra算法或Bellman-Ford算法根据您的权重约束计算单源最短路径。
给定一个无向加权图，2个节点之间的长度是整数。
如何打印图中具有最小距离的对节点。如果有多对，则全部打印出来
假设我们正在无向加权图 G 上寻找简单路径（无重复顶点）。
两个顶点u和v之间的最小距离路径数量最多可达(n-2)条！ （具有零权重边的完整图，从 u 开始并在 v 结束的每个排列都是有效的最小距离路径）。
尽管如此，如果您设法创建一个新图 G'，它具有与 G 相同的顶点并且其边属于某个最小值，则您可以计算出此类路径的数量或回溯以找到每条路径G.
中 u 和 v 之间的距离路径构建 G' 的简单方法是：
- 计算从u开始的单源最短路径并保持距离数组(du)。
- 计算从 v 开始的单源最短路径并保持距离数组 (dv)。
- 使用来自 G 的所有节点和零条边创建 G'。
- 对于 G 中的每条边 <x、y>（<x 的权重, y> 是 w), 如果 du[x] + w + dv[y] == du[v] 或 du[y] + w + dv[x] == du[v] 那么
如果您在第 4 步强制边缘方向并且没有零权重循环，则 G' 是 DAG（有向无环图）。您可以使用 DAG 属性 来计算 G' 中 u 和 v 之间的最小距离路径的数量，并且作为 sidequest 证明这样的答案是等于原问题的答案。此外，如果从 u 回溯，只要它找到 v 那么你就会获得 u 和之间的最小距离路径v 中 G.
您可以使用dijkstra算法或Bellman-Ford算法根据您的权重约束计算单源最短路径。