Algorytm Dijkstry a Drzewo List

Question

Witam. Mam problem z zastosowaniem algorytmu Dijkstry do drzewa list gdzie każde drzewo przechowuje nazwę wierzchołku oraz wskaźnik do listy w której każdy element zawiera odległość  do innego wierzchołka,który wskazywany jest przez wskaźnik do drzewa. Widziałem kilka różnych implementacji tego algorytmu, ale zupełnie nie wiem jak go dostosować pod mój problem oraz jak poruszać się po drzewie (na myśl przychodzi mi rekurencja)? Najlepiej jakby było to z użyciem std::priority_queue.

Comments

drzewa list gdzie każde drzewo przechowuje nazwę wierzchołku oraz wskaźnik do listy w której każdy element zawiera odległość  do innego wierzchołka,który wskazywany jest przez wskaźnik do drzewa

Um, trochę trudno mi to ogarnąć... Jak się to drzewo mapuje na zwykły graf? Co to w ogóle jest za drzewo?

---

struct Nazwy
{
	std::string NazwaElementu;
	Nazwy* Prawy;
	Nazwy* Lewy;
	Odleglosc* Odleglosci;
};
struct Odleglosc
{
	int kilometry;
	Nazwy* Polaczenie;
	Odleglosc* Nastepny;
};

Do drzewa normalnie dodaje elementy w sposób alfabetyczny. I oczywiście ta lista może zawierać kilka różnych połączeń tzn. Element o nazwie A  może mieć listę która zawiera wartości np. 5,10,15 i wskazuje na element B,C,D. 

---

Ale po co jest to drzewo? Co ma reprezentować?

Czy to w zamierzeniu ma być normalny graf, czy coś innego?

---

...OK, domyślam się. Drzewo jest tylko po to żeby mapować nazwę na obiekt wierzchołka.

Trochę... dziwny zapis drzewa, ale OK, bo to nic nie zmienia. Zaraz napiszę odpowiedź.

---

Takie jest założenie zadania. Samo drzewo reprezentuje nazwę elementu i samo w sobie nie jest grafem. Grafem stanie się dopiero wtedy kiedy dodamy właśnie listę, w której dzięki wskaźnikowi na element tego drzewa będziemy wiedzieć, jakie mamy połączenia oraz odległości między nimi, również przechowane w tej liście

Answer 1

oraz jak poruszać się po drzewie

Nie musisz. Dijkstry nie interesuje to drzewo (może poza opcjonalną inicjalizacją która potrzebuje listę wszystkich wierzchołków grafu), interesuje go tylko mapowanie wierzchołek->sąsiedzi, które u Ciebie jest w linked listach.

Użyję jako wzorzec pseudokod z Wikipedii;

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9          prev[v] ← UNDEFINED                    // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev
Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if alt < dist[v] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation).[

W Twoim przypadku, wierzchołki to wskaźnik Nazwy*. 

Tak naprawdę jedyna część która jest zależna od Twojej reprezentacji grafu to:

16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v) 

Ta pętla

for each neighbor v of u:

to po prostu pętla po Twojej linked liście u->Odleglosci.

A to

length(u, v) 

to jest pole "kilometry" w Twojej liście.

I na oko to tyle.

Comments

Jaki jest odpowiednik decrease_priority w C++?

---

W standardowym std::priority_queue nie ma. Patrz ta odpowiedź:

https://stackoverflow.com/a/9210662/2468469

(Są też alternatywne rozwiązania, jak niżej jest opisane w Wikipedii; można użyć innej struktury zamiast priority queue na stertach i "zmniejszać priorytet" usuwając i dodając element od nowa*; albo w ogóle nic nie usuwać tylko za każdym razem dodawać węzeł do kolejki - będą duplikaty o różnych priotytetach, ale je można odrzucić tuż po wyciągnięciu z kolejki zaglądając do zbioru już odwiedzonych wierzchołków; to jest czasem nazywane "lazy deletion": https://stackoverflow.com/a/27305600/2468469)

(*osobiście jak takie rzeczy implementowałem, to właśnie byłem leniem i używałem posortowany std::vector wierzchołków zamiast kolejki na stertach, z którego usuwałem i dodawałem. Choć ostatnio w Pythonie napisałem z "lazy delete" bo tak mi było najprościej)