• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm Dijkstry a Drzewo List

VPS Starter Arubacloud
0 głosów
253 wizyt
pytanie zadane 26 grudnia 2019 w C i C++ przez Dawid Penderewski Nowicjusz (120 p.)
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.
komentarz 26 grudnia 2019 przez adrian17 Ekspert (344,100 p.)

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?

komentarz 26 grudnia 2019 przez Dawid Penderewski Nowicjusz (120 p.)
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. 

komentarz 26 grudnia 2019 przez adrian17 Ekspert (344,100 p.)
Ale po co jest to drzewo? Co ma reprezentować?

Czy to w zamierzeniu ma być normalny graf, czy coś innego?
komentarz 26 grudnia 2019 przez adrian17 Ekspert (344,100 p.)
...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ź.
komentarz 26 grudnia 2019 przez Dawid Penderewski Nowicjusz (120 p.)
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

1 odpowiedź

0 głosów
odpowiedź 26 grudnia 2019 przez adrian17 Ekspert (344,100 p.)

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.

komentarz 27 grudnia 2019 przez Dawid Penderewski Nowicjusz (120 p.)

 

Jaki jest odpowiednik decrease_priority w C++?

komentarz 27 grudnia 2019 przez adrian17 Ekspert (344,100 p.)
edycja 27 grudnia 2019 przez adrian17

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)

Podobne pytania

+1 głos
3 odpowiedzi 1,427 wizyt
0 głosów
1 odpowiedź 412 wizyt
0 głosów
0 odpowiedzi 362 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...