Informatiker Board | Algorithmen | Dijkstra

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Dijkstra - Algorithmus

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Dijkstra - Algorithmus

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Erstsemestler
unregistriert

Dijkstra - Algorithmus

Zitatantwort auf diesen Beitrag erstellen

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 :-)

Erstsemestler hat dieses Bild (verkleinerte Version) angehängt:

13.01.2015 15:54

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:

__________________
Syntax Highlighting fürs Board (Link)

13.01.2015 16:10

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Erstsemestler
unregistriert

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 :-)

13.01.2015 18:59

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

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 Augenzwinkern

Die englische Wikipedia hat recht gute Erklärungen zu vielen Standardalgorithmen.

Gruß,
ED

18.01.2015 17:05

Nehmen Sie ed209 in Ihre Freundesliste auf

Erstsemester
unregistriert

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?

27.01.2015 21:07

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

27.01.2015 21:19

Erstsemester
unregistriert

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

27.01.2015 21:22

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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).

__________________
Syntax Highlighting fürs Board (Link)

27.01.2015 21:24

Erstsemester
unregistriert

Besten Dank :-)

27.01.2015 22:05

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Dijkstra - Algorithmus