Patrzyłem na to, co robią zawodnicy Mario AI Competition , a niektórzy z nich zbudowali całkiem zgrabne boty Mario, wykorzystując algorytm ścieżki A * (A-Star). ( Wideo Mario A * Bot w akcji ) Moje pytanie brzmi: jak wypada A-Star w porównaniu z Dijkstrą? Patrząc na nie, wydają się...
Czy ktoś może mi powiedzieć, dlaczego algorytm Dijkstry dla najkrótszej ścieżki z jednego źródła zakłada, że krawędzie muszą być nieujemne. Mówię tylko o krawędziach, a nie o ujemnych cyklach
Próbuję zrozumieć, dlaczego algorytm Dijkstry nie będzie działał z ujemnymi wagami. Czytając przykład na Shortest Paths , próbuję rozgryźć następujący scenariusz: 2 A-------B \ / 3 \ / -2 \ / C Ze strony internetowej: Zakładając, że wszystkie krawędzie są skierowane od lewej do prawej,...
Oba mogą być użyte do znalezienia najkrótszej ścieżki z jednego źródła. BFS wbiega O(E+V), a Dijkstra wbiega O((V+E)*log(V)). Poza tym widziałem, że Dijkstra używał bardzo podobnie jak w protokołach routingu. Zatem po co używać algorytmu Dijkstry, skoro BFS może zrobić to samo...
Jaka jest dokładna różnica między algorytmami Dijkstry i Prim? Wiem, że Prim poda MST, ale drzewo wygenerowane przez Dijkstrę będzie również MST. Więc jaka jest dokładna różnica?
Nauczyłem się, że algorytm Dijkstry był następujący while pqueue is not empty: distance, node = pqueue.delete_min() if node has been visited: continue else: mark node as visited if node == target: break for each neighbor of node: pqueue.insert(distance + distance_to_neighbor,...
Mam wykres nieukierunkowany z około 100 węzłami i około 200 krawędziami. Jeden węzeł jest oznaczony jako „początek”, jeden to „koniec”, a kilkanaście jest oznaczonych jako „mustpass”. Muszę znaleźć najkrótszą ścieżkę na tym wykresie, która zaczyna się na „początku”, kończy na „końcu” i...