pythonnetworkx

Is there a NetworkX algorithm to find the longest path from a source to a target?


I need to find a longest path in an unweighted graph from s to t.

I am using NetworkX, which has an algorithm for finding a longest path in a directed, acyclic graph, but I am not able to specify the source and the target nodes.

I have not been able to find any info online, but it seems like such an obvious algorithm to have laying around. Is there any way I can do this?


Solution

  • "[T]he longest path problem is the problem of finding a simple path of maximum length in a given graph."[1]

    NetworkX has a simple_paths module, that contains the function all_simple_paths.

    Below is one solution for finding the longest simple paths between two nodes.

    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)
    

    Output

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

    [1] Wikipedia contributors. "Longest path problem." Wikipedia, The Free Encyclopedia. Available from: https://en.wikipedia.org/wiki/Longest_path_problem. Accessed 8 November 2020.