[Rabusek]

Mirki, ważne pytanie:
Miałem w treści zadania: Wypisz wierzchołki grafu w kolejności w jakiej będą przetwarzane w alg. Djikstry

Miałem dość prosty graf, gdzie przejscie bylo jedno. Z wierzchołka połączonego z 4 innymi do jednego z nich (bo najkrótsza droga tędy prowadziła). Najkrotsza droga z A do G

Pytanie, czy PRZETWARZANE oznacza że każdy był sprawdzany, czy oznacza ścieżkę? Ogólnie to wypisałem wszystkie krawędzie (bo przecież djikstra musi wszystkie sprawdzić), bo logicznym dla mnei było, że każdy jest przetwarzany. Czy może jednak PRZETWARZANY oznacza taki przez który algorytm przechodzi i tyle?

Mój strzał to było A G D C E
Podobno odpowiedź to A G :/

#pytanie #algorytmy #informatyka troche #programowanie

[Arveit]

@Rabusek: a czy graf był skierowany, czy nie? Z g do d nie ma kosztu, to jak tam ma iść?

[Rabusek]

@Arveit: jakie eznaczenie ma droga z g do d skoro idziemy z A do G, i już tu widać że najkrótsza to A->G? Powiedzmy ze tam było 6

[Arveit]

@Rabusek: aha nie zauważyłem, że to jest g a nie b xD faktycznie, w takim razie najtańsza droga z A do G to 2 z A do G. Skoro doszedł do G, to nie odwiedza innych.

[Rabusek]

@Arveit: No ale czy nie musi "przetworzyć" innych żeby wiedzieć że idzie do G?
Teoretycznie podkreśliłem A G (xD) przy wypisywaniu wierzchołków więc jeśli tak, to po prostu przy sprawdzaniu bede sie bronić że to była ta odpowiedź, dlatego jest podkreślona

[Arveit]

@Rabusek: szczerze to juz nie pamiętam, z 5 lat temu to gówno miałem xd

[Rabusek]

@Arveit: Ja dzisiaj rano, we wtorek będzie "sprawdzanie egzaminu", stąd pytanie xD

[P.....3]

@Rabusek: Przetwarzany oznacza, ktore sprawdzał, inaczej to pytanie jest trochę bez sensu.

[Arveit]

@Rabusek: z tego co pamiętam, to Dijkstra znajduje najkrótszą ścieżkę poprzez odwiedzenie każdego z wierzchołków, więc Twoja odpowiedź byłaby poprawna. A G to już najkrótsza ścieżka.

[Rabusek]

@Porana123: Dla pewności spisałem wszystkie zadania 1:1 na kartce żeby w domu ogarnąć, i na bank jest przetworzone. No nic, jak dostane jeszcze jedno potwierdzenie to tak będę się bronić.

[sdaniel]

@Rabusek: Dijkstra nie musi sprawdzić wszystkich. Przeanalizuj sobie dokładnie: http://eduinf.waw.pl/inf/alg/001_search/0138.php

[Rabusek]

@sdaniel: ale musi PRZETWORZYĆ wszystkie 4 żeby wiedzieć, że A->G jest najkrótsze. Jeśli PRZETWORZY tylko A->G to przecież nie będzie w ogóle znać wartości A->C->D->G czy A->D->G, bo nawet nie podejrzy tych c/d/e

[P.....3]

@Rabusek: W tym pytaniu trudnością nie jest wypisanie wierzchołków tylko wypisanie ich w dobrej kolejności. Ja bym dał odpowiedź w stylu 'C D E G, gdyż używam porządku alfabetycznego dla wierzchołków'. Dijkstra na tym grafie a szczególnie dla A -> G to generalnie jakiś żart.

[Rabusek]

@Porana123: Mnie martwi że wykładowca stwierdził, iż poprawna odpowiedź to AG, z czym sie totalnie nie zgadzam - wszystko tu zależy właśnie o interpretacji słowa przetwarzać :/

[sdaniel]

@Rabusek: Popatrz na stronkę, do której wysłałem link. Myślę, że jeśli chodzi o przetwarzanie wierzchołka, to z pewnością chodzi o ten, który zdejmujesz ze zbioru Q, dodajesz do zbioru S i sprawdzasz jego sąsiadów. Każda iteracja Dijkstry dotyczy jednego wierzchołka.
Rozumiem, że pewne zamieszanie może spowodować implementacja, np.: jeśli masz w jakiejś strukturze przedstawiającej wierzchołek również informacje, gdzie można z niego dojść i z jaką wagą, to teoretycznie "nie dotykasz" tych

[superbybak]

@Rabusek:
zaczynasz od wrzucenia wierzchołka początkowego A do kolejki Q. Kolejka zawiera pary (wierzchołek, długość ścieżki) i jest posortowana po długości ścieżki:
Q = (A, 0)

Potem "przetwarzasz" wierzchołek A, pobierając go z kolejki i wrzucając wszystkich jego sąsiadów do kolejki:
Q = (G, 2) (D, 5) (C, 10) (E, 23)

Potem "przetwarzasz" następny wierzchołek, czyli ten pierwszy w kolejce: wierzchołek G. Ponieważ to wierzchołek docelowy, a posortowanie kolejki (w połączeniu