Czy istnieje optymalny algorytm do znalezienia najdłuższej najkrótszej ścieżki w sieci?

Mam duży zestaw sieci liniowych i chciałbym znaleźć dwa końce każdej sieci, które są najbardziej od siebie oddalone wzdłuż sieci (na poniższym obrazku byłoby to od D do K). Rozwiązaniem tego problemu dla brutalnej siły jest obliczenie najkrótszej ścieżki w sieci dla każdej pary pochodzenia, ale mam setki sieci z tysiącami końców, więc obliczenie każdej możliwej ścieżki jest dość ciężkie.

Czy istnieje optymalny sposób na obliczenie tego bez użycia brutalnej siły? Czy mogę wykluczyć niektóre punkty na podstawie sprytnych zasad?

EDYCJA: Dodałem ilustrację najdłuższej ścieżki wspomnianej przez @Alex Tereshenkov w celu wyjaśnienia mojego pytania. Czarna ścieżka jest wynikiem algorytmu najdłuższej ścieżki (najdłuższa ścieżka bez powtarzania wierzchołków). W moim przypadku wyobraź sobie, że wchodzisz do sieci z dowolnej litery i musisz jechać do innej litery tak szybko, jak to możliwe. Które dwie litery są najtrudniejsze do połączenia?

Myślę, że możesz szukać średnicy wykresu swojej sieci. Istnieje kilka pytań dotyczących stackexchange, które wspominają ten temat, np .:

• Złożoność czasowa znalezienia średnicy wykresu
• Dobry algorytm do znajdowania średnicy (rzadkiego) wykresu?
• Co oznacza średnica sieci?
• Różnica między średnicą wykresu a najdłuższą ścieżką wykresu

Większość algorytmów sugeruje najpierw obliczenie „wszystkich par najkrótszych ścieżek” i wybranie najdłuższej z nich, ale znalazłem post na blogu autorstwa Koushika Narayanana, który sugeruje alternatywne podejście, które może być bardziej optymalne (nie sprawdziłem), które iteruje po każdym wierzchołku i znajduje najodleglejszą parę:

Możemy obliczyć ścieżkę z wierzchołka V1 w taki sposób, że jest to najkrótsza ścieżka między V1 a jednym z wierzchołków i jest dłuższa niż najkrótsza ścieżka między dowolnym innym wierzchołkiem. Zobacz ten post dla algorytmu. Następnie możemy iterować przez każdy wierzchołek i znaleźć najdłuższą ścieżkę z każdym wierzchołkiem jako korzeniem. Kiedy już mamy listę najdłuższych najkrótszych ścieżek, możemy znaleźć tę, która ma maksymalną wartość i zwrócić ją.

Według strony Wikipedii Problem najdłuższej ścieżki , ten problem

... jest trudny do NP, co oznacza, że ​​nie można go rozwiązać w czasie wielomianowym dla dowolnych grafów, chyba że P = NP. Znane są również wyniki silniejszej twardości pokazujące, że trudno jest je oszacować. Jednak to rozwiązanie ma liniowy czas dla skierowany graf acykliczny, co ma istotne zastosowanie w znalezieniu ścieżki krytycznej w problemach planowania.

Jeśli pracujesz z (lub możesz przedstawić swój wykres jako DAG ), networkxpakiet Python pozwoli ci go obliczyć. Poszukaj funkcji dag_longest_path.

Jeśli czegoś mi nie brakuje, musisz obliczyć długość między węzłami wykresu i posortować je, co niestety będzie działało tylko w czasie liniowym , czyli nie ma na to wydajnego algorytmu.