Programowanie dijkstra

11

Jak wypada porównanie algorytmu Dijkstry i A-Star?

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ę podobne. …

154 algorithm artificial-intelligence graph a-star dijkstra

8

Dlaczego algorytm Dijkstry nie działa dla krawędzi o ujemnej wadze?

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 wagi.

121 algorithm shortest-path dijkstra

8

Ujemne wagi z wykorzystaniem algorytmu Dijkstry

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, jeśli zaczniemy od A, algorytm …

113 algorithm dijkstra shortest-path graph-algorithm

4

Po co używać algorytmu Dijkstry, skoro Breadth First Search (BFS) może zrobić to samo szybciej?

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 szybciej?

110 algorithm graph dijkstra breadth-first-search

15

Różnica między algorytmami Prim i Dijkstra?

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?

97 algorithm graph dijkstra minimum-spanning-tree prims-algorithm

3

Dlaczego algorytm Dijkstry używa klawisza zmniejszania?

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, neighbor) Ale czytałem trochę na temat algorytmu i wiele wersji, …

95 algorithm data-structures priority-queue graph-algorithm dijkstra

10

Znajdź najkrótszą ścieżkę na wykresie, która odwiedza określone węzły

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 przechodzi przez wszystkie węzły „mustpass” (w dowolnej kolejności). …

84 algorithm graph-theory dijkstra

Pytania otagowane jako dijkstra