是否有 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 日。

Answer 2

将边权重乘以 -1（如果它们一开始就没有权重，则将它们全部算作最初的权重为 1）。然后使用bellman-ford作为最短路径（dijkstra不是为了在负权重边缘上工作而构建的，但仍然会给你答案，只是有时它们会错）。只要你没有任何负循环，这应该相当于找到你的最长路径。