Overclocker Opublikowano 22 Listopada 2005 Zgłoś Opublikowano 22 Listopada 2005 Czy w algorytmach Dijkstry i Bellmana-Forda dla wyszukiwania najkrotszej drogi w grafie generowanym na macierzy duży wpływ ma ilośc krawędzi grafu ?? czy moze ilosc krawedzi ma znikomy wpływ, a liczy sie tylko ilośc wierzchołków ??? Jak ktoś zna odpowiedz to bede wdzieczny za informacje. Pozdrawiam. Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Sam Sung Opublikowano 26 Listopada 2005 Zgłoś Opublikowano 26 Listopada 2005 Jeśli kolejka priorytetowa wierzchołków jest implementowana przy pomocy zwykłej tablicy liniowej, to złożoność algorytmu Dijkstry jest O(V^2 + E) - jak widać, decydujące znaczenie ma ilość wierzchołków. Jednak dla grafów rzadkich można zmodyfikować ten algorytm stosując kopiec binarny, wtedy złożoność wynosi O(E lgV), o ile każdy wierzchołek jest osiągalny ze źródła. (Z tym, że dla dużych grafów rzadkich nie ma sensu stosować reprezentacji macierzowej, o której wspominałeś.) Z kolei algorytm Bellmana-Forda ma złożoność O(VE). Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
