Pytania o algorytmiczne problemy znalezienia najkrótszych ścieżek między węzłami na grafie.
Jaka jest różnica między algorytmem minimalnego drzewa opinającego a algorytmem najkrótszej ścieżki? W mojej klasie struktur danych omówiliśmy dwa algorytmy minimalnego drzewa opinającego (Prim i Kruskala) oraz jeden algorytm najkrótszej ścieżki (Dijkstry). Minimalne drzewo opinające to drzewo...
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki...
Na nieważonym wykresie bezkierunkowym z wierzchołkami i krawędziami E, takimi jak 2 V > E , jaki jest najszybszy sposób znalezienia wszystkich najkrótszych ścieżek na wykresie? Czy można to zrobić szybciej niż Floyd-Warshall, który jest O ( V 3 ), ale bardzo szybki na iterację?V.VVmiEE2 V.>...
Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że
Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G ′G = ( V, E)G=(V,E)G=(V,E)sol′= ( V, E′)G′=(V,E′)G'=(V, E')miEEmi′E′E'Θ ( | V|...
Muszę znaleźć cykl ujemny na ukierunkowanym wykresie ważonym. Wiem, jak działa algorytm Bellmana Forda i który mówi mi, czy istnieje możliwy do osiągnięcia cykl ujemny. Ale nie określa go wprost. Jak uzyskać rzeczywistą ścieżkę cyklu?v1,v2,…vk,v1v1,v2,…vk,v1v1, v2, \ldots vk, v1 Po zastosowaniu...
Pomyślałem więc, że należy do tego (choć nieco podstawowego) pytania: Powiedzmy, że mam wykres wielkości 100 węzłów ułożonych we wzór 10x10 (pomyśl szachownica). Wykres jest nieukierowany i nieważony. Poruszanie się po wykresie wymaga przesunięcia o trzy pola do przodu i jedno pole w prawo lub w...
Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie...
Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych. Dostępne są...
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu...
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i...
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby...
Algorytm Bellmana-Ford, określa najkrótszą ścieżkę ze źródła, do pozostałych wierzchołków. Początkowo odległość między a wszystkimi innymi wierzchołkami jest ustawiona na . Następnie obliczana jest najkrótsza ścieżka od do każdego wierzchołka; dzieje się tak w przypadku iteracji . Moje pytania...
Funkcja heurystyczna to ...h(n)h(n)h (n) Spójne, jeśli szacowany koszt od węzła do celu nie jest większy niż koszt kroku do jego następcy plus szacowany koszt od następcy do celu.nnnn′n′n' Dopuszczalne, jeżeli nigdy nie przecenia rzeczywistych kosztów do stanu docelowego.h(n)h(n)h(n) Podręcznik...
Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne. algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych...
Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód: Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi...
Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu [1,…,K][1,…,K][1,\dots, K] gdzie KKK jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do...
Czy algorytm Dijkstry jest wykorzystywany w nowoczesnych systemach wyszukiwania tras, takich jak mapy Google czy satnav w samochodzie? Jeśli nie, to czym
Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do...
Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka vvv tak, że dla każdego u ≠ vu≠vu \ne v jest co najwyżej jedna ścieżka z vvv do uuu. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego...