J
Jan_noAccount
Gast
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:
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?
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,
....
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?