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

user_14444770 0
Viewed 1740

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?

networkx python
1 Answers

"[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.

user_11644650
Related