Algorytm znajdowania centrum grafu


(Adam Kasprzak) #1

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


(enedil) #2

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|)