ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Graphentheorie > Kürzeste Wege:

Dijkstra-Algorithmus

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

In diesem Abschnitt wird der Dijkstra-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.

Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.

Methode

Algorithmus von Dijkstra

Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten $a$. Alle Pfeile seien mit $k(i,j)$ bewertet. Gesucht wird der kürzeste Weg zwischen dem Startknoten und allen anderen Knoten des Diagraphen.

Sei $D(i)$ die kürzeste Entfernung vom Startknoten $a$ zum Knoten $i$, $V(i)$ der unmittelbare Vorgänger von Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Knoten $i$ und die Menge $M$ die Menge einer bestimmten Auswahl von Knoten.

Initialisierung:

$M = \{a \}$

$D(a) = 0$ und $D(i) = \infty$ für alle Knoten $i \neq a$.

$V(i) = - $ für alle Knoten $i$.

Iteration:

1. Schritt: Auswahl eines Knotens $K \in M$ mit $D(K) = min \{D(i) | i \in M \}$.

2. Schritt: Gilt für alle Nachfolger $N(i)$ vom Knoten $K$: $D(K) + k_{Kj} < D(j)$, so wird $D(j) = D(K) + k_{Kj}, V(j) = K$ gesetzt und der Knoten $j$ wird mit in die Menge $m$ aufgenommen.

3. Schritt: Der ausgewählte Knoten $K \in M$ wird aus der Menge entfernt.

Die Schritte 1-3 werden so lange wiederholt bis gilt $M = \{ \}$.

Die Vorgehensweise soll im Folgenden anhand eines Beispiels demonstriert werden.

Anwendungsbeispiel: Dijkstra-Algorithmus

Beispiel Dijkstra-Algorithmus

Beispiel

Gegeben sei der obige Diagraph. Für diesen soll nach dem Dijkstra-Algorithmus der kürzeste Weg von einem Startknoten zu allen anderen Knoten bestimmt werden.

Begonnen wird mit der Initialisierung:

Als Startknoten wird der Knoten 1 gewählt:

$M = \{1 \}$,

$D(1) = 0$,

$D(i) = \infty$ für die Knoten $i = 2,3,4,5,6$ und

$V(i) = -$ für alle Knoten $i = 1,2,3,4,5,6$.


Das Ganze wird in eine Tabelle eingetragen:

$i$    $1$       $2$       $3$       $4$       $5$       $6$   
$D(i)$            $0$    $\infty$    $\infty$    $\infty$    $\infty$    $\infty$   
$V(i)$            $-$ $-$ $-$ $-$ $-$ $-$
$M$             $x$

In der obigen Tabelle ist die Initialisierung eingetragen. Dabei wurde als Startknoten der Knoten 1 gewählt. Gekennzeichnet ist dies in der letzten Zeile mit einem $x$. Dem Startknoten 1 wird $D(1) = 0$ zugeordnet, allen anderen Knoten $D(i) = \infty$. $V(i)$ ist zunächst für alle Knoten leer. 

Es kann nun mit der 1. Iteration begonnen werden.

1. Iteration

1. Schritt: 

Zunächst wird ein Knoten $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befindet sich zunächst der Startknoten 1, also $K = 1$. 

2. Schritt: 

Es werden nun alle Nachfolger von Knoten 1 betrachtet. Die Nachfolger von Knoten 1 sind Knoten 2 und 3. 


Knoten 2:

Es wird dann der kürzeste Weg des Startknotens $D(1) = 0$ zur Pfeilbewertung des Nachfolgerknotens addiert:

$D(1) + k_{12} = 0 + 120 = 120$. 

Das Ergebnis wird mit dem kürzesten Weg des Nachfolgerknotens $D(2) = \infty$ verglichen:

$D(1) + k_{12} < D(2)$

$120 < \infty$.

Ist das Ergebnis (hier: 120) kleiner als der kürzeste Weg des Nachfolgerknotens (hier: $\infty$) so wird der kürzeste Weg des Nachfolgerknotens gleich dem Ergebnis gesetzt.

Es gilt also $120 < \infty$ und demnach wird $D(2) = 120$ gesetzt. Der Vorgänger von Knoten $2$ ist demnach Knoten $1$:

$V(2) = 1$.


Knoten 3:

Für den Knoten 3 gilt dieselbe Vorgehensweise:

$D(1) + k_{13} = 0 + 30 = 30 < \infty$

$D(3) = 30$.

$V(3) = 1$.

3. Schritt: 

Der Knoten 1 welcher sich in $M$ befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

Die neue Tabelle ergibt sich zu:

$i$    $1$       $2$       $3$    $4$ $5$ $6$
$D(i)$             $0$ $120$ $30$ $\infty$ $\infty$ $\infty$
$V(i)$             $-$ $1$ $1$ $-$ $-$ $-$
$M$             $x$ $x$
2. Iteration

1. Schritt: 

Zunächst wird ein Knoten $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befinden sich die Knoten 1 und 2. Den kürzesten Weg besitzt Knoten 3 mit $D(3) = 30$. Dieser wird ausgewählt.

2. Schritt: .

Es werden nun alle Nachfolger von Knoten 3 betrachtet. Die Nachfolger von Knoten 1 sind Knoten 4 und 5. 

Knoten 4:

$D(3) + k_{34} < D(4)$

$30 + 100 = 130 < \infty$

$D(4) = 130$.

$V(4) = 3$.

Knoten 5: 

$D(3) + k_{35} < D(5)$

$30 + 45 = 75 < \infty$

$D(5) = 75$.

$V(5) = 3$.

3. Schritt: 

Der Knoten 3 welcher sich in $M$ befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

$i$    $1$       $2$       $3$       $4$       $5$       $6$   
$D(i)$             $0$ $120$ $30$ $130$ $75$ $\infty$
$V(i)$             $-$ $1$ $1$ $3$ $3$ -
$M$             $x$ $x$ $x$
3. Iteration

1. Schritt: 

Zunächst wird ein Knoten $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befinden sich die Knoten 2, 4 und 5. Den kürzesten Weg besitzt Knoten 5 mit $D(5) = 75$. Dieser wird ausgewählt.

2. Schritt: 

Es werden nun alle Nachfolger von Knoten 5 betrachtet. Die Nachfolger von Knoten 5 sind Knoten 4 und 6. 

Knoten 4:

$D(5) + k_{54} < D(4)$

$75 + 35 = 110 < 130$

$D(4) = 110$.

$V(4) = 5$.

Knoten 6: 

$D(5) + k_{56} < D(6)$

$75 + 40 = 115 < \infty$

$D(6) = 115$.

$V(6) = 5$.

3. Schritt: 

Der Knoten 5 welcher sich in $M$ befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

$i$    $1$       $2$       $3$       $4$       $5$       $6$   
$D(i)$             $0$ $120$ $30$ $110$ $75$ $115$
$V(i)$             $-$ $1$ $1$ $5$ $3$ $5$
$M$             $x$ $x$ $x$

4. - 6. Iteration

Es wird Knoten $4$ mit den Nachfolgern 2 und 6 gewählt. Die kürzesten Wege der Nachfolgerknoten werden nicht verändert, da:

$D(4) + k_{42} > D(2)$: $110 + 80 > 120$. Der Vorgänger bleibt Knoten $1$.

$D(4) + k_{46} > D(6)$: $110 + 40 > 120$. Der Vorgänger bleibt Knoten $5$.

Der Knoten $4$ wird aus $M$ entfernt. 

$i$    $1$       $2$       $3$       $4$       $5$       $6$   
$D(i)$             $0$ $120$ $30$ $110$ $75$ $115$
$V(i)$             $-$ $1$ $1$ $5$ $3$ $5$
$M$              $x$ $x$

Es wird der Knoten $6$ mit den Nachfolgerknoten 4 gewählt. Der kürzeste Weg von Knoten 4 wird nicht verändert:

$D(6) + k_{64} > D(4)$: $115 + 35 > 110$. Der Vorgänger bleibt Knoten $5$.

Der Knoten 6 wird aus $M$ entfernt. 

$i$    $1$       $2$       $3$       $4$       $5$       $6$   
$D(i)$             $0$ $120$ $30$ $110$ $75$ $115$
$V(i)$             $-$ $1$ $1$ $5$ $3$ $5$
$M$             $x$

Es wird der Knoten $2$ mit den Nachfolgerknoten $3$ gewählt. Der kürzeste Weg von Knoten $3$ wird nicht verändert:

$D(2) + k_{23} > D(3)$: $120 + 35 > 30$. Der Vorgänger bleibt Knoten $1$.

Der Knoten 2 wird aus $M$ entfernt. 

Es kann nun der kürzeste Weg vom Startknoten aus zu den einzelnen Knoten aus der Tabelle abgelesen werden. Wird zum Beispiel der Weg zum Knoten 4 gesucht, so muss man die Tabelle rückwärts lesen:

$4 - 5 - 3 - 1$

Der Knoten 4 hat als Vorgänger Knoten 5, dieser hat als Vorgänger Knoten 3 und dieser hat als Vorgänger Knoten 1.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen