检查从顶点 v 到另一个顶点 w 的所有路径是否具有相同的长度
Check if all paths from a vertex v to another vertex w are of the same length
我有一个连通图 g，有 n 个顶点和 m 个边。
每条边都可以从两个方向遍历，从一个方向遍历权重为正，从另一个方向遍历权重为负
所以对于每个边 u -> v 权重 w 存在一个边 v -> u 权重 -w.
我的目标：
对于给定的顶点v，检查是否存在返回v（一个循环）的路径，使得该路径的边权重之和不等于0.如果存在这样一条路径则输出这条路径的最小边数，否则输出"all cycles are fine".
示例：
一个示例，其中从 v 到 v 的所有路径总和为 0。输出为 "all cycles are fine":
一个示例，其中存在从 v 到 v 的路径，其边缘总和不等于 0。在这个例子中，这样一条路径的最小边数是 4：
我目前的做法：
这个问题似乎等同于检查从给定顶点 v 到任何其他顶点 w 的所有路径是否长度相等，如果为真则 "all cycles are fine"，否则我输出打破条件的最短周期的长度。我很难找到一种有效的算法来测试这种情况。
检查是否存在通过顶点 A 的 "wrong cycle" 的简单算法是 运行 来自 A 的 BFS，然后查看哪些顶点 B 以不同的成本至少被访问两次.如果不存在 B，则所有循环都是好的，否则存在大小为（直到第一次访问 B 的边）+（直到以不同成本访问 B 的边）的坏循环。这个 BFS 最多访问每个顶点两次，所以复杂度仍然是线性的。
因此，这个问题可以通过图中每个顶点的 BFS 来解决。当然，也许这可以提高效率；什么是足够的取决于 n 和 m 的大小。
我有一个连通图 g，有 n 个顶点和 m 个边。
每条边都可以从两个方向遍历，从一个方向遍历权重为正，从另一个方向遍历权重为负
所以对于每个边 u -> v 权重 w 存在一个边 v -> u 权重 -w.
我的目标：
对于给定的顶点v，检查是否存在返回v（一个循环）的路径，使得该路径的边权重之和不等于0.如果存在这样一条路径则输出这条路径的最小边数，否则输出"all cycles are fine".
示例：
一个示例，其中从 v 到 v 的所有路径总和为 0。输出为 "all cycles are fine":
一个示例，其中存在从 v 到 v 的路径，其边缘总和不等于 0。在这个例子中，这样一条路径的最小边数是 4：
我目前的做法：
这个问题似乎等同于检查从给定顶点 v 到任何其他顶点 w 的所有路径是否长度相等，如果为真则 "all cycles are fine"，否则我输出打破条件的最短周期的长度。我很难找到一种有效的算法来测试这种情况。
检查是否存在通过顶点 A 的 "wrong cycle" 的简单算法是 运行 来自 A 的 BFS，然后查看哪些顶点 B 以不同的成本至少被访问两次.如果不存在 B，则所有循环都是好的，否则存在大小为（直到第一次访问 B 的边）+（直到以不同成本访问 B 的边）的坏循环。这个 BFS 最多访问每个顶点两次，所以复杂度仍然是线性的。
因此，这个问题可以通过图中每个顶点的 BFS 来解决。当然，也许这可以提高效率；什么是足够的取决于 n 和 m 的大小。