Graphenalgorithmen

Dijkstra-Algorithmus

 aufwärts

Problem

Gegeben ist ein ungerichteter, zusammenhängender Graph mit einer Kantengewichtung. Gesucht sind die kürzesten Wege von einem bestimmten Startknoten zu allen anderen Knoten des Graphen.

Der Floyd-Algorithmus löst das Problem mit der Zeitkomplexität Θ(n3). Er berechnet aber sogar die kürzesten Wege von allen Knoten zu allen anderen Knoten.

Wenn nur die kürzesten Wege von einem bestimmten Startknoten zu allen anderen Knoten gesucht sind, lässt sich das Problem mit dem Algorithmus von Dijkstra [Dij 59] in Zeit Θ(n2) lösen.

Idee

Der Algorithmus zur Berechnung der kürzesten Wege baut schrittweise den Baum der kürzesten Wege auf. Jedes Mal, wenn ein neuer Knoten u zum Baum hinzukommt, muss die Menge der Kandidaten aktualisiert werden. Hierzu werden alle Nachbarknoten von u durchlaufen. Dabei kommt es nun darauf an, wie viele Nachbarknoten die Knoten des Graphen typischerweise haben. Sind dies viele, etwa Θ(n) , so kann "alle Nachbarknoten durchlaufen" ersetzt werden durch "alle Knoten durchlaufen".

Damit ergibt sich ein einfacheres und schnelleres Verfahren, das zudem ohne Prioritätenliste auskommt, das Verfahren von Dijkstra.

Es stellt sich heraus, dass sich der Dijkstra-Algorithmus durch eine geringfügige Modifikation des Algorithmus zu Berechnung eines minimalen Spannbaums ergibt. Die Änderung betrifft die Wahl des nächsten Kandidaten, der zu dem jeweils schon erzeugten Baum hinzugenommen wird. Bei der Berechnung des Baums der kürzesten Wege wird der Kandidat genommen, der den kürzesten Abstand zum Startknoten hat. Dieser Abstand ergibt sich aus dem Gewicht der Kante zwischen dem Kandidaten und einem Knoten des schon erzeugten Baumes plus dem Abstand dieses Knotens vom Startknoten.

Algorithmus Kürzeste Wege

Der Algorithmus zur Berechnung der kürzesten Wege ist fast identisch mit dem Algorithmus zur Berechnung eines minimalen Spannbaums. Die einzigen Abweichungen sind in der folgenden informellen Darstellung fett gedruckt gekennzeichnet.

 

Algorithmus Kürzeste Wege (Dijkstra)
Eingabe:Zusammenhängender ungerichteter Graph G = (V, E) mit Kantengewichtung w, Startknoten s
Ausgabe:Baum der kürzesten Wege in G vom Startknoten s zu allen anderen Knoten; zu jedem Knoten v bedeuten distance(v) die kürzeste Entfernung zum Startknoten und predecessor(v) den zugehörigen Vorgänger im Baum
Methode:
  1. für alle v Element V wiederhole
    1. setze distance(v) = unendlich

    setze u = s

    setze T = {u}

    setze distance(u) = 0

    setze predecessor(u) = -1

    solange T ≠ V wiederhole

    1. für alle v nicht Element T mit (u, vElement E wiederhole
      1. wenn distance(v) > distance(u) + w(u, v) dann
        1. setze distance(v) = distance(u) + w(u, v)

          setze predecessor(v) = u

      suche u nicht Element T mit distance(u) minimal

      setze T = T vereinigt {u}

 

Das entsprechende Java-Programm ergibt sich mit den angegebenen Änderungen unmittelbar aus dem Programm zur Berechnung eines minimalen Spannbaums.

Literatur

Originalartikel:
[Dij 59]E.W. Dijkstra: A Note on two Problems in Connexion with Graphs. Numerische Mathematik 1, 269-271 (1959)
Bücher

 

Weiter mit:   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 03.03.2002   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik