Mam duży, połączony, rzadki wykres w formie listy przyległości. Chciałbym znaleźć dwa wierzchołki, które są tak daleko od siebie, jak to możliweśrednica wykresu i dwa osiągające go wierzchołki.

Interesuje mnie ten problem zarówno w przypadku nieukierunkowanych, jak i ukierunkowanych, dla różnych aplikacji. W ukierunkowanym przypadku oczywiście zależy mi na ukierunkowanej odległości (najkrótsza skierowana ścieżka od jednego wierzchołka do drugiego).

Czy istnieje lepsze podejście niż obliczanie najkrótszych ścieżek dla wszystkich par?

Edytować: „Najdalej jak to możliwe” mam na myśli „najdłuższą najkrótszą ścieżkę” - to znaczy maksimum nad wszystkimi parami wierzchołków o najkrótszej odległości od jednej do drugiej.