在一个有向图中寻找不同路径数量的算法

Question

我有一个有向图，我可以使用什么算法来找到两个特定顶点之间不同无环路径的数量，并计算任何路径在这些不同路径中被使用的最大次数？ 如果两条路径访问不同数量的顶点或以不同的顺序访问顶点，则它们是不同的路径。

可能重复：
图算法查找两个任意顶点之间的所有连接

- Pranav

---

依我看，这并不需要成为一个重复的问题。知道值的数量（整数）和知道所有值的差别（一组节点列表）。对于我的目的来说，甚至只有数量的合理猜测（上界）也可以，所以对我来说这不是一个重复的问题。 - danatel

图形算法以查找两个任意顶点之间的所有连接根本不是重复的问题：枚举和计数是不同的问题，有向图与无向图也是不同的。关于计算简单路径的复杂度，请参见在有向图中计算两个节点之间简单路径数量有多难？ 在[cs.se]上。 - Gilles 'SO- stop being evil'

我同意Danatel的观点 - 对于大型图形，枚举所有可能路径是不可取的。 - Andrew Buss

Answer 1

如果您遵循稍微修改过的Dijkstra算法，就可以得到一种全对方案。

解释：从u到v的路径是以下内容的总和：

1.不经过w的从u到v的路径 2.通过w的路径=从u到w的路径数*从w到v的路径数

将矩阵初始化为零，除非有一条从i到j的边缘(即为1)。 然后，以下算法将给出结果（所有对路径计数）。

for i = 1 to n:
    for j = 1 to n:
        for k = 1 to n:
            paths[i][i] += paths[i][k] * paths[k][j]

毋庸置疑： O(n^3) 渴望阅读一个简单的解决方案。 :)

- ThisIsMeMoony

---

这个解决方案没有正确处理路径不能有循环的要求。 - hugomg

这是一个修改过的Bellman-Ford算法，不是一个修改过的Dijkstra算法（因此存在环问题）。 - Jules Olléon