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.
Gast
#1121898
ja das habe ich schon gelesen. habe nur keine ahnung wie ich bei der aufgabe anfangen soll.
Gast
#1121977
Na, mit R1, deswegen heißt der "Startrouter"...
ja und dann?
Gast
#1123124
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).
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...
Angehängte Dateien:
-
spannbaum.png
(3,7 KB)
Gast
#1123356
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
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.
Hat den mein "Denkanstoß" geholfen und konntest du es Nachvollziehen?
Gast
#1123716
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