Overclocker Napisano 22 Listopada 2005 Zgłoś Napisano 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 More sharing options...
Sam Sung Napisano 26 Listopada 2005 Zgłoś Napisano 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 More sharing options...
