Methoden Kürzester Weg im Graphen -.-

[Jan_noAccount]

Ich weiß, dazu gibts viele Anfragen in google, aber bisher hab ich wirklich keine richtige Lösung gefunden -.-



Ich suche eine Methode, um den kürzesten Weg von A nach B im Graphen zu finden.
Lösungsansätze:
-Bei jedem Knoten eine Liste zu erstellen, in die die nachbarn + gewicht gespeichert werden.
Über rekursivstruktur ablaufen, eben immer prüfen, welcher zurückgegebenen Werte kleiner ist, und als result speichern.
Bsp mit Baumstruktur:

linkerNachbar
rechterNachbar

jeweils im Rechten und linken N die methode aufrufen, bis man ganz unten ist, dann zurückgeben (ihr kennt ja rekursiv )

Immer den kürzeren der linken und rechten Teilbäume nehmen, weitergeben,

....​

Problem:

Gewichte + Nachbarn werden nur in einer "Adjazenzmatrix" gespeichert, d.h die Knoten wissen gar nicht, welche nachbarn sie haben -.- (und ich glaub, wir sollen das so lassen^^)

Man könnt ja immer durch die Zeile des aktuellen Knoten laufen, speichern, in welche spalte was eingetragen ist, die gemerkten Knoten in den Zeilen suchen, usw.

Nur hab ich keine Ahnung, wie man das kurz hinbekommt, bzw auch nicht, wie mans lang hinkriegt.

Wie nutzt man da die Rekursion? Wie würdet ihr da durchlaufen?

 

[Firephoenix]

Ein passender Algorythmus wäre dieser hier:
Dijkstra-Algorithmus ? Wikipedia
bzw alternativ bei negativen Kanten der hier:
Bellman-Ford-Algorithmus ? Wikipedia
oder falls du Luftlinien schätzen kannst (bei matrixdarstellung wohl eher nicht)
A*-Algorithmus ? Wikipedia

In welcher Form du den Graphen speicherst ist übrigens egal, die Algorythmen sind auf alle gängigen Datenstrukturen für Graphen anpassbar und auch aus einer Adjazenzmatrix kannst du ablesen welche Nachbarn ein Knoten hat.

Entsprechende Lösungsansätze bietet dann der eigene Kopf oder Google.

Gruß

 

[Jan_noAccount]

Mein Dijkstra sucht jetzt immer den kürzesten weg weg von einem Knoten.
Nur, wenn von dem Knoten keine Kante zu einem anderen existiert, die kürzer ist als die zum vorgänger, hab ich ne endlosschleife^^

Selbst wenn ich besuchte Knoten speicher, geh ich da nicht mehr hin, aber wie garantiert dijkstra, dass ich den kürzesten weg finde?

Bsp:
a->f ?

a->b 5
a->c 7
--> geht von a -> b

b->d 4
b->e 3
--> geht von b -> e

e->f 1
---> insgesamt 9

aber:
c->f 1

---> a->c->f wär mit 8 kürzer^^
wird aber gar nicht kontrolliert.

 

[SlaterB]

in deinem Text ist das so, aber warum sollte das etwas über Dijkstra aussagen?
Dijkstra würde anders vorgehen und selbstverständlich den kurzen Weg finden

wenn ich mir 'Informeller Algorithmus' in
Dijkstra-Algorithmus ? Wikipedia
anschaue,
dann würde in der Tat erst Knoten a untersucht, und dann so wie du es hast Knoten b, weil der der nahste zu a ist,

aber es ist nicht gesagt, dass dann nur noch die Nachbarn von b in Frage kommen,
nach der Untersuchung von b besteht die Liste der unbesuchten Knoten aus
c 7
d 9 (5+4)
e 8 (5+3)

genau nach Algorithmus geht es nun nicht mit e weiter, sondern erstmal wird c untersucht, dann zu f ein Abstand von 8 festgestellt,
auch das, obwohl ein erster Weg bis zum Ziel gefunden ist, müsste noch nicht unbedingt das Ende sein,
falls weitere unbesuchte Knoten unter 8 vorhanden sind, könnten die schneller zu f führen und untersucht werden,
hier nicht der Fall (also in der Implementation kann es schon sein dass e untersucht wird,
offizielles Ende ist ja genau dann wenn f als aktueller Knoten ausgewählt wird)

 

[Landei]

Hier ein recht ordentlich geschriebener Dijkstra: Dijkstra's algorithm (Java) - LiteratePrograms