Dijkstra

Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Dijkstra

Beitrag von Hallo » 15. Sep 2016 11:31

Hi,
Warum wird f ab 5. Iteration erst zu 9 und g ab der 5. ungleich infinty ?

Anfangsknoten ist i.
Dateianhänge
Screen Shot 2016-09-15 at 11.30.44.png
Screen Shot 2016-09-15 at 11.30.44.png (14.22 KiB) 581 mal betrachtet
Screen Shot 2016-09-15 at 11.30.31.png
Screen Shot 2016-09-15 at 11.30.31.png (41.35 KiB) 581 mal betrachtet

Nicca
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 7. Jun 2016 13:35

Re: Dijkstra

Beitrag von Nicca » 15. Sep 2016 11:54

Ich kann das jetzt anhand des Screenshots nicht so gut nachvollziehen, aber grundsätzlich schaust du ja am Anfang (Iteration 0), wie groß die Kantenwerte zu den Nachbarn des Startknoten sind. Dann setzt du sozusagen als Zwischenpunkt den Knoten, zu dem die kürzeste Entfernung besteht. Dadurch ergeben sich neue Knoten, die du nun über diesen Zwischenpunkt erreichen kannst.
Bei deiner Iteration 5 ist es dann wohl so, dass sich zu g das erste Mal überhaupt ein Weg ergibt (vorher hatte g keinen Nachbarn, der bereits als Zwischenknoten aufgenommen war) und gleichzeitig zu f nun ein kürzerer Weg als vorher möglich ist.

Ich weiß nicht, ob diese Erklärung verständlich ist - vielleicht müsste man die Werte nach Iteration 4 sehen, um es besser zu erklären, kann man auf dem Screenshot aber leider kaum erkennen.

VG
Katrin

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: Dijkstra

Beitrag von Hallo » 15. Sep 2016 12:05

Screen Shot 2016-09-15 at 11.30.44.png
Screen Shot 2016-09-15 at 11.30.44.png (14.22 KiB) 564 mal betrachtet

Habe die Screenshots nochmal gemacht. Ich weiß wie Dijkstra grunsätzlich funktioniert, aber mit diesem Iterationsschritt komme ich nicht klar.
Dateianhänge
Screen Shot 2016-09-15 at 11.30.31.png
Screen Shot 2016-09-15 at 11.30.31.png (41.35 KiB) 564 mal betrachtet

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: Dijkstra

Beitrag von Hallo » 15. Sep 2016 12:10

Geklärt ich bin an einer Iteration etwas übersehen :oops: :lol:

Nicca
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 7. Jun 2016 13:35

Re: Dijkstra

Beitrag von Nicca » 15. Sep 2016 12:26

OK ;)

Antworten

Zurück zu „AuD: Arbeit mit Nabla“