Pytanie dotyczące algorytmu dijkstra

Question

Próbuję znaleźć najkrótszą ścieżkę między dwoma węzłami w zestawie danych. I zaimplementowałem algorytm dijkstra i używam go do udowodnienia, że ​​ z dwoma węzłami (jak: Andrew_Card i Dick_Cheney) nie istnieje istnieje ścieżka między źródłem a miejscem docelowym. Jednak znajduję , że mój program jest zabijany przez system operacyjny.

Po debugowaniu okazało się, że problem może być związany z alokacją zasobów w pamięci RAM . Jeśli chodzi o algorytm Dijkstra, jeżeli liczba węzłów, n = 16375503, a następnie wymóg przestrzeń jest

n*n = 16,375,503 * 16,375,503 > 10^{14}. 

Aby uruchomić ten algorytm w pamięci musimy przynajmniej

(10^{14} * 4)/(1024 * 1024 * 1024) = 10^5 GB (approximately equal) 
of RAM. 

Tak, to nie jest można znaleźć najkrótszą ścieżkę, używając dijkstry , jeśli chcemy zachować duży podłączony wykres w pamięci. Proszę mnie poprawić, jeśli się mylę, ponieważ utknąłem na tym od dłuższego czasu? Albo jeśli mógłbym znaleźć jakiś inny możliwy powód, który powinienem sprawdzić, to proszę mnie o to również poinformować.

I realizowany program w C++

Ilość krawędzi = 25.908.132

Answer 1

Jeśli liczba krawędzi jest stosunkowo niska (tak, aby wszystkie krawędzie mogły zmieścić się w głównej pamięci), można po prostu zapisać wykres za pomocą listy przyległości. Wymaga pamięci O(V + E), zamiast O(V^2). Co więcej, możesz użyć algorytmu Dijkstry z kolejką priorytetową. Działa dobrze w przypadku rozrzedzonych wykresów (ma on złożoność w czasie O(E log V)). Takie podejście powinno działać dobrze dla wykresu z wierzchołkami i krawędziami o wartości około 2 * 10^7 (dobra implementacja może łatwo zmieścić się w pamięci głównej i działać przez nie więcej niż kilka minut).

Answer 2

Jeśli potrzebujesz tylko odległość między dwoma węzłami, użyć czegoś jak A*.

Ale jeśli robisz wszystkie punkty najkrótsze ścieżki, to na pewno utkniesz w przestrzeni O(n^2). Znajdujesz odpowiedzi na O(n^2) - tak naprawdę nie możesz zrobić nic lepszego, niż przechowywanie ich wszystkich.

Answer 3

Jeśli chodzi o upewnienie się, że w programie rzeczywiście brakuje pamięci, zapakuj swój callsite w blok try-catch i sprawdź, czy otrzymujesz wyjątek std :: bad_alloc. Dopóki nie zobaczysz wyjątku, który przechwytujesz, nie załóżmy, że która część twojego programu się zawodzi.

Jeśli chodzi o znalezienie najkrótszej trasy między dwoma węzłami, prawdopodobnie powinieneś zdobyć więcej literatury, aby znaleźć to, co jest najbardziej odpowiednie algorytm do twojego przypadku użycia.

A *: http://en.wikipedia.org/wiki/A * _search_algorithm

Skurcz hierarchia: http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

Answer 4

Trzeba znaleźć sposób, aby zmniejszyć liczbę węzłów. Twoja liczba węzłów jest wysoka. Możesz użyć Diagramu Voronoi, aby zmniejszyć liczbę węzłów.

Answer 5

Ulepszanie może polegać tylko na tym, aby przechowywać wierzchołki w kolejce priorytetów. I zaktualizuj kolejkę priorytetową, zamiast dodawać ten sam wierzchołek do kolejki priorytetów.