Route berechnen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:01 Fr 15.02.2008 | | Autor: | LL0rd |
Hallo,
ich stehe gerade vor einem kleinen Problem mit Algorithmen. Ich habe einen Graphen und suche in diesem Graphen nach der kürzesten Verbindung zweier Knoten miteinander. Übersteigt die Kantenzahl einen bestimmten n Wert, so soll die Verbindung als nicht gefunden gelten. Ich habe nun z.B. folgenden Graphen.
(Knoten) -> (Kante zu anderen Knoten)
1 -> 5,6,7
2 -> 7
3 -> 1,2
4 -> 3
5 -> 10
6 -> {} (nix)
Jetzt suche ich nach dem kürzesten Weg (kürzeste Weg = möglichst wenig Knoten passieren) zwischen 1 und 10, ich sehe, dass der kürzeste Weg 1 -> 5 -> 10 ist. Als zweite Suche habe ich 1 -> 6. Ich merke, dass es keine Verbindung gibt.
Soweit die Aufgabenstellung.
Jetzt folgt mein Lösungsansatz:
Ich habe mir nun überlegt, was es denn ähnliches in der Welt gibt und da sind mir die Navigationssysteme eingefallen. Diese arbeiten mit dem Dijkstra-Algorithmus. http://de.wikipedia.org/wiki/Dijkstra-Algorithmus aber bei diesem Algorithmus habe ich zwei Probleme. Zum einen arbeitet er mit gewichteten Kanten. Bei mir ist es nicht der Fall, ok, alle Kanten wären dann mit 1 gewichtet. Aber nun folgt das zweite und auch schwerere Problem. Dieser Algorithmus geht davon aus, dass es tatsächlich immer eine Verbindung zwischen zwei Punkten gibt. Klar, ich kann ihn nach einer bestimmten Kantenlänge abbrechen, aber ob das tatsächlich so effizient ist, ist eine andere Frage.
Deshalb wollte ich nachfragen, ob es noch andere Möglichkeiten gibt, um so etwas lösen zu können.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:48 Fr 15.02.2008 | | Autor: | Gilga |
Dijkstra ist schon richtig. Der Alg. bricht ab wenn es keine Knoten mehr gibt die noch nicht besucht wurden.
Das ganze ist ein Suchproblem.
z.B. Breitensuche(in diesem Fall die einfachste und beste Möglichkeit), Tiefensuche
|
|
|
|
