www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Dijkstra-Algorithmus
Dijkstra-Algorithmus < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Dijkstra-Algorithmus: Vorschlag zur Vorgehensweise
Status: (Frage) beantwortet Status 
Datum: 18:34 So 20.01.2008
Autor: Graph_von_Dijkstra

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:
[]http://www.onlinemathe.de/forum/Dijkstra-Algorithmus-Graphentheorie


        
Bezug
Dijkstra-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 19:59 So 20.01.2008
Autor: Tester0815

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

Bezug
                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:29 So 20.01.2008
Autor: Graph_von_Dijkstra

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


Bezug
                        
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                
Bezug
Dijkstra-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:03 So 20.01.2008
Autor: Graph_von_Dijkstra

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!

Bezug
                                        
Bezug
Dijkstra-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 22:13 So 20.01.2008
Autor: Tester0815

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!

Bezug
                                                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:18 So 20.01.2008
Autor: Graph_von_Dijkstra

Ok, ich probiers gerade mal. Lösung kommt also gleich ;-)

Bezug
                                                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:26 So 20.01.2008
Autor: Graph_von_Dijkstra

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!

Bezug
                                                        
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!)

Bezug
                                                                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:44 So 20.01.2008
Autor: Graph_von_Dijkstra

Super und Danke nochmal!

Bezug
        
Bezug
Dijkstra-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 21:03 So 20.01.2008
Autor: Bastiane

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]


Bezug
                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:43 So 20.01.2008
Autor: Graph_von_Dijkstra

Danke für die Hilfe;-)

Bezug
        
Bezug
Dijkstra-Algorithmus: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Dijkstra-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:43 So 20.01.2008
Autor: Graph_von_Dijkstra

Alles klar. Vielen Dank für die Hilfe!

Ich meine, es nun begriffen zu haben...

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de