# Breitendurchlauf / Dijkstra durch Graph, vereinfacht



## royale (19. Jun 2008)

Hi,
ich habe hier eine kleine Klasse, die einen gerichtete Graphen enthalten soll, welche eine Stadt darstellen.

Städte und Kreuzungen sind als "Knoten"- Klasse definiert. Diese besitzen in sich jeweils eine LinkedList, in welche Elemente der Klasse "Kante", welche die Straßen darstellen sollen. Städte befinden sich immer am Ende einer Straße, Kreuzungen verbinden Straßen untereinander.

Die Knoten (Städte/Kreuzungen) als auch die Straßen in den LinkedListen können seperat ge- und entsperrt werden, falls sich dort jemand bewegt. 

Hoffe, der Code ist einigermaßen verständlich?

Jetzt möchte ich von jedem Knoten aus einen wegsuch- Algorithmus durchführen, der aber nur die nächste zu befahrene Kante (Straße) oder Knoten (Stadt/Kreuzung) ausgibt. An jeder angekommenen Kreuzung soll aufs neue geprüft werden, wo man als nächstes hinfährt, da Knoten bzw. Kanten während der Fahrt zwischenzeitlich von jemand anderm gesperrt werden können, daher brauche ich nicht den ganzen Pfad, sondern den nächsten Knoten/Kante!

Ich steh aber grade ganz stark auf dem Schlauch, am liebsten würde ich ja Dijkstra verwenden, da ich dann die Straßenlängen mit berückstigen kann. Ein normaler Breitendurchlauf würde aber auch reichen..

Grüße,
David


```
import java.util.*;
	
	
	public class geographie  {
		
		//Naechsten anzufahrenden Knoten berechnen
		Kante berechne(Knoten start, Knoten ziel){
						
					
			return null; //Da soll der Roboter hin			
		}		
	}


	class Knoten {
		//Kreuzung oder Stadt
		boolean gesperrt; int nr; String name;
		LinkedList wege = new LinkedList(); //Wo fuehrt ein Weg hin?
			
		
		//Neuen Knoten erzeugen
		Knoten (int nr, String name){
			gesperrt=false;
			this.nr=nr;
			this.name = name;
		}
		
		//Sperren
		void sperrung (){
			this.gesperrt = true;
		}
		
		//Freigeben
		void freigabe (){
			this.gesperrt = false;
		}
		
		//Strasse irgendwohin einfuegen
		void einfuegen (Knoten k){			
			
			if (k!=null){
			
				Kante ziel = new Kante (k);
				wege.add(ziel);
			}			
		}
		
	}

	//Strasse
	class Kante {
		boolean gesperrt; 	Knoten nach;
		
		Kante(Knoten nach){
			this.gesperrt=false;
			this.nach=nach;
		}
		
	   //Sperren
		void sperrung (){
			this.gesperrt = true;
		}
		
		//Freigeben
		void freigabe (){
			this.gesperrt = false;
		}
	}
```


----------



## Gelöschtes Mitglied 5909 (19. Jun 2008)

Und was is da deine konkrete Frage?

Du brauchst erstmal eine "karte" mit den weglängen. Dann musst du noch irgendwie wissen, welcher Knoten mit welchem anderen Knoten verbunden ist. Dann vergleichst du die längen der verbundenen Knoten und fügst den mit der kleinsten länge zu deinem Weg dazu.

Dijkstra funktioniert aber anders, da es den gesamten Weg untersucht. In deinem Fall ist es gut möglich, dass du nicht den kürzesten weg findest, wenn z.b. einmal ein sehr langer Weg gewählt werden muss, weil der vorherige kurz war.

So wie du das machst is es sehr einfach imo, aber eben auch nicht die beste Lösung.

1. Füge bei Kante eine länge ein
2. Baue eine Karte auf, z.b. HashMap<Knoten/Knoten.name, List<Kante>> (equals / hashcode nicht vergessen !) oder nehme direkt eine TreeMap, die kannst du dann nach kante.länge sortieren


----------



## SlaterB (19. Jun 2008)

um es noch mal deutlich zu sagen: wenn man sich nur für die erste Kante vom kürzesten Weg zum Ziel interessiert,
muss man trotzdem praktisch den gesamten kürzesten Weg zu Ziel herausfinden,
ein bisschen kann man schon sparen, etwa durch gewisse Abschätzungen

(wenn man von Berlin nur nach Hamburg und München kommt,
und abschätzen kann, dass der Weg zum Ziel Stuttgart über Hamburg selbst auf Luftlinie (ab Hamburg) mindestens x km sind,
und man von München aus einen Weg y nach Stuttgart mit Gesamtlänge < x  gefunden hat,
dann kann man die noch nicht näher untersuchten Routen über Hamburg streichen,
erste Kante muss also die nach München sein,
egal ob der Weg y nun schon optimal ist oder dort unten in Bayern noch was zu untersuchen ist)


----------



## royale (20. Jun 2008)

raiL hat gesagt.:
			
		

> Und was is da deine konkrete Frage?
> 
> Du brauchst erstmal eine "karte" mit den weglängen. Dann musst du noch irgendwie wissen, welcher Knoten mit welchem anderen Knoten verbunden ist. Dann vergleichst du die längen der verbundenen Knoten und fügst den mit der kleinsten länge zu deinem Weg dazu.



Meine konkrete Frage ist, wie so ein Berechnungsalgorithmus aussehen könnte, um den nächsten anzufahrenen Knoten auszugeben. Das würde in dem Fall auch mit Dijkstra gehen, wenn man in der Klasse "Kante" noch einen double- Wert "Laenge" hinzufügen würde.

Wie die Knoten untereinander verbunden sind, geht ja aus der LinkedList in der Klasse "Knoten" hervor. In diese LinkedList werden Objekte der Klasse "Kante" eingefügt, welche die Straßen von dem aktuellen Knoten zu anderen darstellen. Die Kanten in der LinkedList haben ja eine Verweisvariable "Knoten nach", wo die Zielstadt oder Kreuzung mit vermerkt ist.

Schwierig ist das ganze ja deshalb, da die "kanten-" LinkedList des aktuellen Knotens durchgegangen werden muss, und die Listen der dort vermerkten Zielknoten müssen wiederrum durchgegangen werden, bis man am Ziel angelangt ist. Am Ende hat man dann vom momentanen Standpunkt aus einen vollständigen (kürzesten) Pfad, von dem aber nur der nächste anzufahrene Knoten bzw. Kante ausgegeben werden soll.

Wie ich das jetzt als Code darstellen soll.. puh, sehr komplex! Frage klar? 

Mit Hashtabellen kenn ich micht nicht so aus  Kompliziert oder schön muss es nicht sein, hauptsache, es funktioniert! 

Grüße,
David


----------

