Algorytm znajdowania centrum grafu

Cześć,

Czy znajdzie się na forum osoba, która mogłaby pomóc w temacie algorytmu znajdowania centrum grafu? Temat na zaliczenie przedmiotu :slight_smile:

Nie oczekuję oczywiście gotowego rozwiązania, ale raczej wskazania literatury lub podpowiedzi jak taki algorytm przelać na kod w  C# lub w python’ie.

 

Z góry dzięki. 

 

Adam

Używasz algorytmu najkrótszych ścieżek, chyba najlepiej Dijkstry (gdy wagi są dodatnie), jeżeli bywają ujemne, używasz Bellman-Ford-Moora.

Z tego co pamiętam, to Dijkstra znajdywali najkrótsze ścieżki pomiędzy jednym wierzchołkiem, a każdym innym. Wyznaczasz największą wartość spośród tych odległości (wyszukiwanie liniowe). Dopuki są jeszcze niezbadane wierzchołki, powtarzasz procedurę, jeżeli najdłuższa odległość jest krótsza od dotychczasowego rozwiązania, zastępujesz rozwiązanie tym wierzchołkiem.

Złożoność czasowa:

O(Dijkstry)*O(|E|) = O(|E|^2 + |E|*|V|*log(|V|)