---

Geschrieben von Erstsemestler am 13.01.2015 um 15:54:

  Dijkstra - Algorithmus

Meine Frage:
Hi Leute,

da die Videos auf YouTube wieder einmal unbrauchbar sind, müsstet ihr mir weiterhelfen.

Das Problem findet sich im Anhang :-)

Meine Ideen:
Besten Dank :-)

---

Geschrieben von eulerscheZahl am 13.01.2015 um 16:10:

 

Das Vorgehen ist folgendes:
Der Startknoten A erhält der Wert 0. Alle von ihn aus erreichbaren Knoten erhalten den Wert des Pfads. Du suchst nun den Knoten (bzw. die Knoten) mit dem geringsten Wert. Jetzt gehst du wieder alle Punkte im Graphen durch, die noch nicht verwendet sind und gibst ihnen als Wert den des bereits erreichten Nachbarknotens plus dem der Verbindung. Kannst du einen Knoten auf verschiedenen Wegen erreichen, nimmst du das Minimum. Kannst du einen Knoten gar nicht erreichen (er grenzt an keinen bereits erreichten an), ignorierst du ihn, dann es er eben im nächsten SChritt dran.Das wiederholst du, bis keine Knoten mehr übrig sind.

Im Anhang sind die bereits festen Werte grün, die zu prüfenden rot.

---

Geschrieben von Erstsemestler am 13.01.2015 um 18:59:

 

Super, klasse. Danke dir. Du schaffst es in 7 Zeilen mir das zu erklären, was ich brauche. Die YouTube-Videos dauern zwischen 10 und 15 Minuten und durchsteigen tue ich überhaupt nicht :-)

---

Geschrieben von ed209 am 18.01.2015 um 17:05:

 

Vergiss youtube videos.
Theoretische Informatik ist abstrakt und du solltest sie auch versuchen abstrakt zu verstehen.
Skizzen können dir zur veranschauchlichung dienen, aber sind viel effektiver wenn Du sie selber anfertigst
Die englische Wikipedia hat recht gute Erklärungen zu vielen Standardalgorithmen.

Gruß,
ED

---

Geschrieben von Erstsemester am 27.01.2015 um 21:07:

 

Hey eulerscheZahl,

ich muss das Thema nochmal aufgreifen. Warum hat beim zweiten Durchlauf (zweites Bild oben rechts) B eine zwei? Muss da nicht auf die 1 von D aufaddiert werden?

---

Geschrieben von eulerscheZahl am 27.01.2015 um 21:19:

 

Es gibt 2 Möglichkeiten, auf B zu kommen:
Einmal über D, dann sind es 1+2=3. Aber es geht auch direkt von A, daher die 2. Man nimmt immer das Minimum.

---

Geschrieben von Erstsemester am 27.01.2015 um 21:22:

 

Und warum wird dann im dritten Bild B ausgewählt? Ausgehend von der Entfernung von D würde ja B und C gehen?

---

Geschrieben von eulerscheZahl am 27.01.2015 um 21:24:

 

Immer erst das mit dem geringsten Wert, vielleicht findet man ja für die anderen eine noch bessere Lösung (siehe C, das geht von 4 auf 3).

---

Geschrieben von Erstsemester am 27.01.2015 um 22:05:

 

Besten Dank :-)