Dijkstra-Algorithmus < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Folgende Tabelle führt die Entfernungen zwischen 6 Städten auf:
A D G L S W
A 0 78 56 73 71 114
D 78 0 132 121 135 96
G 56 132 0 64 85 154
L 73 121 64 0 144 116
S 71 135 85 144 0 185
W 114 96 154 116 185 0
Man bestimme ein Straßennetz minimaler Gesamtlänge, das alle 6 Orte miteinander verbindet.
|
Moin.
Es wäre spitze, wenn mir jemand am praktischen Beispiel die Vorgehensweise des Dijkstra-Algorithmus einfühlsam erklären könnte (am Dienstag steht da so eine Klausur an...). Vielen Dank!
PS: Weiß nicht, ob die Frage bei Kombinatorik richtig gestellt ist.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
![[]](/images/popup.gif) http://www.onlinemathe.de/forum/Dijkstra-Algorithmus-Graphentheorie
|
|
| |
|
Sehr gute Erklärungen liefern wikipedia.org und ne japanische Seite (auf Englisch). Sind bebilderte und animierte Erlklärungen dabei sowie Beispielcode:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
|
|
|
| |
|
Hi,
Danke für deine Antwort. Mit dem wiki-Artikel konnte ich auch schon vorher nix anfangen. Bei mir ist z.B. gar nicht gegeben, in welcher Stadt ich anfange. Wäre das egal?
Eine schrittweise Erklärung wäre (bei) mir sehr hilfreich.
Nochmal danke.> Sehr gute Erklärungen liefern wikipedia.org und ne
> japanische Seite (auf Englisch). Sind bebilderte und
> animierte Erlklärungen dabei sowie Beispielcode:
>
> http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
>
> http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:30 So 20.01.2008 | | Autor: | Tester0815 |
Meines Erachtens passt die Fragestellung nicht ganz zum Dijkstra-Algorithmus.
Das minimale Straßennetz würde ich bestimmen, indem ich jeweils die Summe der Distanzen von einer Stadt zu jeder anderen bilde und diese anschließend vergleiche. Z.B. hat das Straßennetz von A zu jeder anderen Stadt die Gesamtlänge 392 und ist damit optimal (A liegt also am zentralsten) - dann würde je eine Straße die Stadt A mit den anderen verbinden und man hätte ein minimales Straßennetz - allerdings ohne Verwendung des Dijkstra-Algorithmus.
Wenn jede Stadt mit jeder verbunden werden soll, dann könnte man den Dijkstra-Algorithmus anwenden, und würde von einer Stadt jeweils die kürzesten Verbindungen zu allen anderen Städten berechnen - dann hätte man jeweils die optimalen Strecken.
Dijkstra funktioniert grob gesagt so (Am Beispiel des Weges A zu W):
- Vom Startknoten A werden die möglichen Verbindungen verglichen:
G (56)
S (71)
L (73)
D (78)
W (114)
- die Kürzeste wird genommen, in dem Fall nach G (56)
- vom Knoten G wird wiederum verglichen:
S (71)
L (73)
D (78)
W (114)
G-L (120)
G-S (141)
G-D (188)
G-W (210)
- S wird gewählt (71)
L (73)
D (78)
W (114)
G-L (120)
G-S (141)
G-D (188)
G-W (210)
...
=> Siehe auch die Bilder bei Wikipedia; vom zweiten auf den dritten Schritt wird der linke Ast relaxt, vom dritten auf den vierten Schritt der rechte Ast, da die Strecke kürzer ist als die Strecke am linken Ast
Wie das Wikipedia-Beispiel zeigt, ist eine direkte Verbindung meist nicht vorhanden und der Algorithmus "hangelt" sich an den Ästen entlang, bis er am Ziel ist; in deinem Fall sind ja alle Strecken bekannt und direkt nutzbar, weshalb vom Algorithmus jeweils der kürzeste Weg, also der direkte genutzt würde.
|
|
|
| |
|
Erstmal: Entschuldigung für die Verwirrung!
Also, die Aufgabe heißt tatsächlich so, wie ich sie reingesetzt habe. Nun dachte ich aber fälschlicherweise, das löst man mit Dijkstra. Man man aber wohl nicht...
Also die Aufgabe ist:
Man bestimme ein Strßennetz minimaler Gesamtlänge, das alle 6 Orte miteinander verbindet.
Perdon y muchas gracias!
|
|
|
| |
|
Hi,
wie schon geschrieben, würde ich das lösen, indem ich jeweils die Summe der Distanzen von einer Stadt zu jeder anderen bilde und diese anschließend vergleiche. Z.B. hat das Straßennetz von "A" zu jeder anderen Stadt die Gesamtlänge 392 und ist damit optimal ("A" liegt also am zentralsten) - dann würde je eine Straße die Stadt "A" mit den anderen verbinden und man hätte ein minimales Straßennetz.
Also für die Stadt "D" z.B. 78 + 132 + 121 + 135 + 96 = 562 - so hast du von "D" ausgehend zu jeder Stadt eine Verbindung mit der Gesamtlänge von 562. Das musst du noch für die anderen Städten errechnen, dann vergleichen und hast dann eine optimale Lösung!
|
|
|
| |
|
Ok, ich probiers gerade mal. Lösung kommt also gleich 
|
|
|
| |
|
Also, das Problem stellt sich mir jetzt doch eher so dar:
es soll nicht eine direkte Verbindung durch alle Städte geben (also auf einer Linie aufgereiht), sondern das kürzeste Straßennetz, in denen alle Städte drin sind. Das kann bedeuten, dass von der Stadt A bspw. 3 Straßen abgehen, und von L nur eine (aber über die eine kommt man auch von L nach bspw. S, dann eben über A).
Ist das so verständlich?
Leute, ich glaube, ich habs geschnackelt!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:34 So 20.01.2008 | | Autor: | Tester0815 |
So - dann geb ich dir mal folgende Literatur zur Hand, die dir sicher weiterhelfen wird:
http://de.wikipedia.org/wiki/Minimal_spannender_Baum
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
(Siehe auch Antwort von koepper!)
|
|
|
| |
|
Hallo!
> Folgende Tabelle führt die Entfernungen zwischen 6 Städten
> auf:
> A D G L S W
> A 0 78 56 73 71 114
> D 78 0 132 121 135 96
> G 56 132 0 64 85 154
> L 73 121 64 0 144 116
> S 71 135 85 144 0 185
> W 114 96 154 116 185 0
>
> Man bestimme ein Straßennetz minimaler Gesamtlänge, das
> alle 6 Orte miteinander verbindet.
>
>
> Moin.
>
> Es wäre spitze, wenn mir jemand am praktischen Beispiel die
> Vorgehensweise des Dijkstra-Algorithmus einfühlsam erklären
> könnte (am Dienstag steht da so eine Klausur an...). Vielen
Ok, ich probier's mal. Wo du anfängst, sollte wohl egal sein, da du ja sowieso überall mal hinmusst... Sagen wir also, du fängst bei A an. Dann betrachtest du alle "Nachbarn" von A, in deinem Fall sind das wohl alle. Die nimmst du in eine Menge - nennen wir sie R - auf. Von diesen betrachtest du jetzt den mit dem kürzesten Abstand zu A - also G (mit 56). Dies ist dein neuer Knoten und zu diesem ist der kürzeste bereits bestimmt, wir können diesen Knoten aus der Menge R rausnehmen und ihn in die Menge G stecken (in dieser sollen dann alle Knoten stehen, zu denen der kürzeste Weg bereits bestimmt ist). Nun betrachten wir also G und von dort aus wieder alle Nachbarn. Diese Nachbarn fügen wir wieder zu R hinzu und suchen uns das Minimum aus der ganzen Menge R. Ach ja, A kommt nicht in diese Menge, da A schon betrachtet wurde. Es werden nur immer Elemente eingefügt, die noch nicht komplett abgearbeitet wurden, als für die der kürzeste Weg noch nicht bestimmt ist. Und von A zu A ist der kürzeste Weg 0, das hätte ich vllt am Anfang erwähnen sollen.
Der kürzeste Weg ist nun also zu L (mit 64). Den nimmst du wieder aus R raus und fügst ihn in S ein. Dann betrachtest du wieder die Nachbarn usw.
Aber mir fällt gerade auf, dass man damit die Aufgabe gar nicht löst und die obige Matrix wahrscheinlich schon die Lösung eines Dijkstra-Algos ist - kann das sein?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Danke für die Hilfe
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:45 So 20.01.2008 | | Autor: | koepper |
Hallo,
ich glaube wir haben hier ein grundlegendes Problem:
Das von dir geschilderte Problem ist das sogenannte MST (Minimum Spanning Tree). Die wichtigsten Algorithmen dafür kommen von Prim und Kruskal. Sie laufen in Polynomzeit.
Der Algorithmus von Dijkstra liefert für Graphen mit nichtnegativen Knotenentfernungen den kürzesten Weg von einem beliebigen Knoten zu allen anderen. Dabei kommt auch ein aufspannender Baum heraus, aber mit festgelegter Wurzel.
Dijkstra ist also hier zur Lösung nicht geeignet und du solltest noch einmal die Aufgabe genau anschauen, was tatsächlich gefordert ist.
LG
Will
|
|
|
| |
|
Alles klar. Vielen Dank für die Hilfe!
Ich meine, es nun begriffen zu haben...
|
|
|
|
