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 » |
|