python - 是否有 NetworkX 算法可以找到从源到目标的最长路径？

Question

我需要在未加权图中找到从s到t的最长路径。

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

我无法在网上找到任何信息，但它似乎是一个非常明显的算法。我有什么办法可以做到这一点吗？

Answer 1

[T]最长路径问题是在给定图中找到最大长度的简单路径的问题。”^{[ 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 日访问。