| Autor |
Beitrag |
    
Wonkyfox (Wonkyfox)
Neues Mitglied
Benutzername: Wonkyfox
Nummer des Beitrags: 4
Registriert: 10-2000
| | Veröffentlicht am Montag, den 26. Januar, 2004 - 12:07: | 
|
So hier die Aufgabe:
Wenden die den Algorithmus von Dijkstra zur Bestimmung der kürzesten Wege im folgenden gerichteten Graphen an: V = {1, 2, . . . , 6}, der Graph ist vollständig, das heißt, von jedem Knoten gibt es eine Kante zu jedem anderen Knoten, und die Kantenlängen sind cij = 3^(j−i) für i < j und cij = i − j für i > j. Der Startknoten ist der Knoten 2.
Kann mir mal jemand erklären was mit c j i gemaint ist das verstehe ich nicht ...
wenn das jemand könnte wäre super
lg
ronny |
Wonkyfox (Wonkyfox)
Neues Mitglied
Benutzername: Wonkyfox
Nummer des Beitrags: 5
Registriert: 10-2000
| | Veröffentlicht am Montag, den 26. Januar, 2004 - 12:08: |
|
ups da ist mir doch ein fehler passiert 
cij = 3^(j-i) für i < j und cij = i - j für i > j.
so ist es richtig.
danke
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 226
Registriert: 10-2001
| | Veröffentlicht am Montag, den 26. Januar, 2004 - 13:07: |
|
Hallo Wonkyfox,
stelle Dir alle Kanten als Adjazenzmatrix dar, dann ist i die Spalte und j die Zeile.
Bsp.: für V={1,2,3}
...1 2 3
1 0 1 1
2 1 0 1
3 1 1 0
Also Knoten 2 (i=2) ist verbunden mit 1 und 3 (j=1 und j=3).
Jetzt könntest Du in die Matrix die Kantenlängen eintragen (nach Deinen Regeln):
j\i 1 2 3
1 0 1 2
2 3 0 1
3 9 3 0
z.B. Kante (1,3) i=1, j=3 => i<j => Länge = 3^(3-1) = 9
Und das klapperst Du jetzt mit dem Algorithmus von Dijkstra durch (siehe http://www.mcgods.de/fun/1904/node8.html)
Dadurch findest Du die kürzesten Wege in einem Graph - allerdings ist der Dijkstra besser für Graphen mit wenigen Kanten geeigenet.
Wenn Du den Algorithmus mit Hilfe der Adjazenzmatrix löst ist der Aufwand auch O(n²).
Cu Onkel Murray |
Wonkyfox (Wonkyfox)
Junior Mitglied
Benutzername: Wonkyfox
Nummer des Beitrags: 6
Registriert: 10-2000
| | Veröffentlicht am Montag, den 26. Januar, 2004 - 13:22: |
|
Danke vielmals |
Wonkyfox (Wonkyfox)
Junior Mitglied
Benutzername: Wonkyfox
Nummer des Beitrags: 7
Registriert: 10-2000
| | Veröffentlicht am Montag, den 02. Februar, 2004 - 07:47: |
|
Ich habe ja jetzt diese Adjazenzmatrix erstellt:
( Aufgabenstellung siehe oben )
ji 1 2 3 4 5 6
1 0 1 2 3 4 5
2 3 0 1 2 3 4
3 9 3 0 1 2 3
4 27 9 3 0 1 2
5 81 27 9 3 0 1
6 243 81 27 9 3 0
So, jetzt sind das ja die Gewichte. Aber was ich nicht verstehe ist, das würde ja bedeuten, dass von jedem Knoten zum anderen eine Kante hin- und eine Kante zurückführ, die unterschiedliche Gewichte hat, stimmt das? Als Besp. vom Knoten 1 geht eine Kante mit Gewicht "1" zum Knoten 2 und vom Knoten 2 geht eine Kante mit Gewicht "3" zum Knoten 1. Stimmt das so, wie ich das interpretiere?
In der Aufgabenstellung heißt es, der Graph soll vollständig sein, dass heißtvon jedem Knoten gibt
es eine Kante zu jedem anderen Knoten. Heißt das es muss diese Kante mindestens existieren oder
wirklich nur eine? Denn lt. meinem Bsp. wären es zwischen allen Knoten 2 Kanten ...
Wäre nett wenn ihr mir das noch beantworten könntet.
Gruß
Ronny |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 230
Registriert: 10-2001
| | Veröffentlicht am Montag, den 02. Februar, 2004 - 09:08: |
|
Hallo Wonkyfox,
jepp, Deine Annahme ist vollommen richtig. Du bist in einem gerichteten Graphen und jeder Knoten hat 5 "raus"-zeigende und 5 "rein"-zeigende Kanten.
(vollständig meint eigentlich nur die "raus"-zeigenden Kanten - wenn ich nicht irre)
Ein einfaches Beispiel:
Du mußt von A nach B (und zurück). Hin fährst Du mit dem Auto und zurück fliegst Du im Flugzeug. Wenn jede Kante die Zeit (oder den Preis) enthält die Du brauchst, dann sind deren Gewichte tatsächlich verschieden.
Onkel Murray |
Wonkyfox (Wonkyfox)
Junior Mitglied
Benutzername: Wonkyfox
Nummer des Beitrags: 8
Registriert: 10-2000
| | Veröffentlicht am Montag, den 02. Februar, 2004 - 14:27: |
|
bin wie immer zu dank verpflichtet
danke
ronny |
