有没有一种NetworkX算法可以找到从源节点到目标节点的最长路径？

Question

我需要在一个无权重的图中找到从s到t的最长路径。

我正在使用NetworkX，该库有一个用于在有向无环图中查找最长路径的算法，但我无法指定源节点和目标节点。

我没有找到任何相关信息，但这似乎是一个很显然的算法。我有没有办法做到这一点？

- n00bster

---

你能否简单地反转边的权重，然后使用networkx内置的解决方案之一查找最短路径？ - Mathieu

我想这应该可行，因为我的网络是无权重的，所有边的权重都将简单地为-1。 - n00bster

唯一的问题是，Dijkstra算法在存在环的情况下会失败。 - n00bster

这个问题没有有效的算法（它是NP难问题）。这里有一首关于它的歌曲：https://www.youtube.com/watch?v=a3ww0gwEszo - Joel

Answer 1

“最长路径问题是指在给定的图中找到一条最大长度的简单路径的问题。”（引自1）

NetworkX有一个“simple_paths”模块，其中包含函数“all_simple_paths”。

以下是一种解决方案，用于找到两个节点之间的最长简单路径。

from typing import List
import networkx as nx 

def longest_simple_paths(graph, source, target) -> List[List]:
    longest_paths = []
    longest_path_length = 0
    for path in nx.all_simple_paths(G, source=source, target=target):
        if len(path) > longest_path_length:
            longest_path_length = len(path)
            longest_paths.clear()
            longest_paths.append(path)
        elif len(path) == longest_path_length:
            longest_paths.append(path)
    return longest_paths


G = nx.complete_graph(4)
longest_paths = longest_simple_paths(G, source=0, target=3)
if longest_paths:
    print(f"Longest simple path contains {len(longest_paths[0])} nodes")
    print(longest_paths)

输出

Longest simple path contains 4 nodes
[[0, 1, 2, 3], [0, 2, 1, 3]]

---

^[1] 维基百科贡献者。"最长路径问题"。维基百科，自由的百科全书。可从以下链接获取：https://en.wikipedia.org/wiki/Longest_path_problem。访问日期为2020年11月8日。

- Christopher Peisert

---

应该强调，在大型网络中找到最长路径没有已知的高效算法（而且很不可能存在快速算法）。 - Joel

然而，在网上有一些地方，人们声称可以在伪多项式时间内完成它。 - n00bster