Dijkstra - Algorithmus

13.01.2015, 15:54	Auf diesen Beitrag antworten »
Erstsemestler	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 :-)


13.01.2015, 16:10	Auf diesen Beitrag antworten »
eulerscheZahl	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.
13.01.2015, 18:59	Auf diesen Beitrag antworten »
Erstsemestler	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 :-)
18.01.2015, 17:05	Auf diesen Beitrag antworten »
ed209	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
Anzeige

27.01.2015, 21:07	Auf diesen Beitrag antworten »
Erstsemester	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:19	Auf diesen Beitrag antworten »
eulerscheZahl	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.
27.01.2015, 21:22	Auf diesen Beitrag antworten »
Erstsemester	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:24	Auf diesen Beitrag antworten »
eulerscheZahl	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).
27.01.2015, 22:05	Auf diesen Beitrag antworten »
Erstsemester	Besten Dank :-)

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »