Wie berechne ich mit dem Dijkstra-Algorithmus den kürzesten Weg in einem Netzwerk?

Question

Ich habe folgendes Netz gegeben mit den Routern A-F:

A mit B verbunden Kosten 2

A mit C verbunden Kosten 4

A mit F verbunden Kosten 7

B mit D verbunden Kosten 2

D mit F verbunden Kosten 1

F mit C verbunden Kosten 3

F mit A verbunden Kosten 7

F mit E verbunden Kosten 3

C mit E verbunden Kosten 1

Wie berechne ich mit Dijskstra den kürzesten Pfad zu allen Wegen von A aus zu den anderen Routern? Wäre wirklich super, wenn ihr mir da helfen könnt! Mir ist hier der Rechenweg wichtig bzw. wie man rangeht.

Answer 1

MathFox,

der Dijkstra-Algorithmus wird für gewöhnlich bei Netzwerken mit OSPF (Open Shortest Path First) zum Routing genutzt und die Netzwerkopologie besteht aus ungerichteten Verbindungen, weshalb die Information "F mit A verbunden Kosten 7" redundant ist, da Du bereits "A mit F verbunden Kosten 7" geschrieben hast.

Es ist zudem immer hilfreich, wenn man sich das Netz einmal aufzeichnet, was ich hiermit nachhole:

Am besten löst man das Problem tabellarisch. Ein Video zum Dijsktra-Algorithmus hat Marvin Pogoda Dir in seiner Antwort bereits gepostet. Ich werde diesen (Algorithmus) nun konkret auf das von Dir beschriebene Netzwerk anwenden. Dabei seien p(X) die Kosten zum Erreichen von Router X und V(X) der Vorgänger von X. K' ist die Menge der bereits besuchten Router: 

Ich hoffe, dass ich Dir damit weiterhelfen konnte!

André, savest8

Answer 2

Hier gibt es eine Erklärung des Algorithmus.

Sehr viele Algorithmen gibt es mehrfach im Internet erklärt an Beispielen. Fürs nächste mal, solltest du zunächst einmal selbst danach schauen.

Comments

Danke. Ja, das hätte ich vorher mal googlen können. Das werde ich zukünftig berücksichtigen.

---

Ich behaupte mal einfach, dass sich 60% der Aufgaben(wenn nicht sogar mehr) durch googlen lösen lassen .

---

Hallo Marvin,

die Schätzung ist durchaus realistisch. Die übrigen 40% repräsentieren wir;-)