Weg zwischen 2 Knoten (XML/JAXB)

[Fawkes]

Hallo,

ich habe ein Baumförmig aufgebautes Netzwerk (XML). Jeder Knoten hat genau einen Vaterknoten und alles geht von einem Wurzelknoten aus.
Jetzt bin ich gerade auf der Suche, nach einer möglichst effizienten Methode, den Weg zwischen 2 beliebigen Knoten zu finden (Durch den Aufbau des Baums, gibt es ja nur einen möglichen Weg zwischen 2 Knoten).
Ich hatte bisher in diese Richtung gedacht:

1: Setze Start bei Startknoten
2: Besuche Vaterknoten
3: Prüfe ob Vaterknoten = Zielknoten
4: Wen nicht füge aktuellen Knoten dem Weg hinzu
5: Prüfe ob aktueller Knoten weitere Kindknoten hat
6: Wen nein: Weiter mit Schritt 2
7: Wenn ja: Besuche Kindknoten
8: Prüfe aktueller Knoten = Zielknoten
9: Wen nein, füge aktuellen Knoten dem Weg hinzu
10: Weiter mit Schritt 5
--
Hier dann das Problem, wen der Wurzelknoten mehr als 2 Kindknoten hat müsste man nun im schlimmsten Fall alle Pfade komplett rauf und runter durchgehen bis man sein Ziel gefunden hat.

Gerade ist mir noch eingefallen, dass das hier auch gehen müsste:
1: Gehe von Startknoten zu Wurzelknoten, merke kompletten Weg
2: Gehe von Zielknoten zu Wurzelknoten, merke kompletten Weg
3: Prüfe ob Start/Zielknoten in Weg von Start/Zielknoten vorkommt
4: Wen ja: Weg gegeben
5: Wen nein: Setze beide Pfade zusammen = Weg

Wäre schonmal eine bessere Lösung, aber evtl. weiß jemand noch etwas besseres. Oder gibt es evtl. schon von JAXB aus eine Methode, die den Weg für einen sucht?

Grüße

 

[Gast2]

Ich würds so machen:
Startknoten A, Zielknoten B
Bestimme Weg W1 von A zur Wurzel, bestimme Weg W2 von B zur wurzel.
Laufe die Wege W1 und W2 Richtung Wurzel, C sei der erste gemeinsame Knoten der beiden Wege.
=> Dein gesuchter Weg ist A->C->B

 

[Fawkes]

Hallo,
danke für die Antwort, das scheint wohl am sinnvollsten

Werde dann versuchen es so umzusetzen.
Grüße
Fawkes

 

[Wildcard]

Schau dir mal den Dijkstra's algorithm an

 

[Gast2]

Der Dijkstra macht hier aber mMn nicht soviel sind, damit wird der komplette Graph durchlaufen um den kürzesten Weg zu finden.
Da es sich hier aber um nen Baum handelt weiß man dass es nur genau einen Weg zwischen zwei Knoten geben kann (wenn man Knoten nur einmal besucht) , der is dann von natur aus schon der kürzeste

Hallo,
danke für die Antwort, das scheint wohl am sinnvollsten.

Ob das das sinnvollste ist kommt immer auf den Baum an. Je nach Tiefe des Baumes kann man noch ein paar weitere Überlegungen anstellen und die Laufzeit verkürzen.

 

[Wildcard]

Stimmt, Fawkes schreibt ja, dass jeder Knoten nur einmal im Baum auftaucht, das vereinfacht die Sache natürlich.