Algorytm Dijkstry

Question

W jaki sposób mogę zmienić klasyczną implementacje algorytmu Dijktstry, żeby ograniczyć zużycie pamięci? Moja implementacja przy założeniu, każdy wierzchołek ma połączenie z każdym, przy tworzeniu tablicy wag krawędzi zużywa ogromne ilości pamięci. W jaki sposób mogę zoptymalizować algorytm by ten zużywał jak najmniej pamięci?

Comments

Czy wagi w tym grafie pełnym spełniają nierówność trójkąta, tj. w(A, B) + w(B, C) >= w(A, C)?

---

przy tworzeniu tablicy wag krawędzi zużywa ogromne ilości pamięci

Ale to nie jest część algorytmu dijkstry, to są dane wejściowe do algorytmu.

---

@adrian17 ma tu rację. Nieważne co byś nie robił te dane i tak musisz wczytać. Nawet dla takich pesymistycznych przypadków jak n^2 krawędzi nie można tu za dużo zdziałać, aby zmniejszyć zużycie pamięci

 

Answer 1

Nie rób połączenia każdego z każdym. Graf zazwyczaj robi się w ten sposób:

vector<pair<int, int> > g[N]; // first - do jakiego wierzcholka, second - waga krawedzi
// wczytywanie
for(int i = 0; i<n; i++){
 int from, to, w;
 cin >> from >> to >> w;
 g[from].push_back({to, w});
 g[to].push_back({from, w});
}