图中两个结点之间的最长路径

Question

这个问题已经有人问过了，但我想对它有一些新的看法（也包括我对它的一个想法）。在

我有一个非循环图（通过使用NetworkX），我需要迭代（出于各种原因）图中的路径。在

我现在要做的是为每个u和v迭代nx.all_simple_paths(G, u, v)，但是如果我得到正确的文档，这个函数的复杂度可能高达O（n！），这不是。。。伟大的。在

所以我的想法是，既然我知道我在图上做什么样的操作，就可以“动态地”得到新的路径。我在脚本的开头创建一个所有路径的列表，然后每当我做一个修改（只能添加一个弧或删除一个弧）时，我会在我的路径列表中搜索哪些路径受到删除弧的影响（并删除它们），以及通过添加新弧可以创建哪些路径（如果我有一个新的弧u -> v，我会查找所有以u结尾的路径，并将它们连接到以v开头的所有路径，因此这些操作的复杂性都是多项式的。在

现在，我想知道在我的问题上我的想法是否正确，你是否有更好的方法来做得更简单。在