Router algorithmus dijkstra

[Frank B. (hoschie2)]

hallo

Man hat ein Netzwerk mit 6 Routern (R1 bis R6). Auf den
Kanten stehen die Kosten von einem Router zum Nachbar-Router. jetzt soll 
man von Startrouter R1 mithilfe des Algorithmus von Dijkstra den 
kürzesten
Pfad zu den Routern R2 bis R6 ermitteln. Stellen das Ergebnis als 
aufspannenden Baum mit R1 als Wurzel dar.

viellecht kann mir ja jemand helfen.

[hans (Gast)]

http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

[Frank B. (hoschie2)]

ja das habe ich schon gelesen. habe nur keine ahnung wie ich bei der 
aufgabe anfangen soll.

[Simon (Gast)]

Na, mit R1, deswegen heißt der "Startrouter"...

[Frank B. (hoschie2)]

ja und dann?

[STK500-Besitzer (Gast)]

Guck dir doch mal die Entfernung von R1 zu R5 an.
Den Weg zwischen R1 und R5 kann über verschiedene Pfade zurückgelegt 
werden.
Aus den verschiedenen Möglichkeiten muß man halt die heraussuchen, die 
am kleinsten ist.

Wie man das als Baum oder so darstellt, weiß ich nicht (bin kein 
Informatiker).

[Läubi .. (laeubi)]

Wenn ich mich nicht vertan hab sieht der Spannbaum so aus...
Du ermittelst einfach mit dem Algorithmus alle Kürzesten Wege

- von 1 nach 2
- von 1 nach 3
- von 1 nach 4
- von 1 nach 5
- von 1 nach 6

Dann streichst du alle Kanten die nicht zu den kürzesten Wegen gehören 
und erhälst den folgenden (gerichteten) Graphen der dir die Wege angibt 
die die man nimmt um immer möglichst geringe Kosten zu haben.

Wobei man das bei dieser Aufgabe shcon fast durch scharfes hinsehen 
erledigen kann, aber zur veranschaulichung des Algorithmus ne ganz nette 
Übung.

P.S. In der Klausur/Prüfung kann ich dir dann leider nicht helfen...

[Simon (Gast)]

Frank:

Du scheinst irgendwie eine komplette Aufschlüsselung und Musterlösung 
anhand Deines Problems zu erwarten. Guck dir Die Wikipedia-Seite an, 
genauer lässt sich das doch gar nicht mehr aufschlüsseln. Da sind sogar 
ausführliche Beispiele da.

Ich nehme mal an, dass das eine Aufgabe aus Deinem Informatik-Studium 
ist. Dir ist überhaupt nicht geholfen, wenn Dir das jemand vorkaut, 
vorverdaut und dann in Dein Gehirn sch***t. Du musst das selber lösen, 
du musst selber nachvollziehen wie der Algorithmus arbeitet, du musst 
selber Hand anlegen.

Wenn Du nach meiner - zugegebenermaßen nicht als hilfreich gemeinten - 
Antwort nur "ja und dann?" fragst, dann schließe ich daraus, dass Du 
exakt keine Lust hast, darüber nachzudenken. Meine Güte, warum studierst 
Du überhaupt?

Ich habe mehr als drei Jahre lang unter anderem versucht, den 
Algorithmus von Dijkstra Studierenden beizubiegen. Diese 
"Kau-mir-gefälligst-vor-damit-ich-nicht-denken-muss"-Haltung ist 
unerträglich. Zeig wenigstens ein bischen Initiative, zum Beispiel indem 
Du sagst, an welchem Schritt es hakt, oder was Du alles schon versucht 
hast, um das Problem zu lösen.

seufz

Grüße,
        Simon

[Frank B. (hoschie2)]

ich sitze schon länger daran, wollte nur ein paar denkanstösse haben um 
es selbst zu lösen und dann nachvollziehen zu können.
ich will ja keine komplette vorgekaute lösung. ich muss es ja in der 
klausur auch seler und alleine lösen können.

[Läubi .. (laeubi)]

Hat den mein "Denkanstoß" geholfen und konntest du es Nachvollziehen?

[Simon (Gast)]

Frank:

Na, dann mal los: Nimm Dein Problem und wende den "Informellen 
Algorithmus" von der Wikipedia-Seite an.

Wenn das nicht klappt, kannst Du ja wenigstens genau beschreiben was Du 
nicht verstanden hast bzw. wo Du auf Probleme gestoßen bist. Dann können 
wir weitersehen.

Grüße,
        Simon