mikrocontroller.net

Forum: PC Hard- und Software Router algorithmus dijkstra


Autor: Frank Busse (hoschie2)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: hans (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Frank Busse (hoschie2)
Datum:

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

Autor: Simon (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na, mit R1, deswegen heißt der "Startrouter"...

Autor: Frank Busse (hoschie2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja und dann?

Autor: STK500-Besitzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Läubi .. (laeubi) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Simon (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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

Autor: Frank Busse (hoschie2)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat den mein "Denkanstoß" geholfen und konntest du es Nachvollziehen?

Autor: Simon (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.