Graphen-Algorithmen

Aus Infostudium Wiki

Inhaltsverzeichnis 1 Floyd-Warshall-Algorithmus 1.1 Floyd 1.2 Warshall 2 Algorithmus von Dijkstra 3 Prim-Algorithmus (Algorithmus von Prim)

Floyd-Warshall-Algorithmus

• All-Pairs Best Path

Floyd

• Er findet die Länge der kürzesten Wege zwischen allen Paaren von Knoten eines gewichteten Graphen.
• Zeitkomplexität O( | V | ³)

Durchführung:

Zunächst eine Kosten-Matrix erstellen, die die Kosten von einem Knoten zu einem anderen auf direktem Wege darstellt. Dann wird versucht, die Knoten nacheinander über einen bestimmten Knoten zu erreichen. Der minimalen Kosten werden immer in die Matrizen eingetragen. Das macht dann Anzahl der Elemente + 1 Matrizen. Die jeweiligen Änderungen werden in einer separaten Matrix vermerkt, um den Weg rekonstruieren zu können.

A_k[i,j]: = min{A_{k − 1}[i,j],A_{k − 1}[i,k] + A_{k − 1}[k,j]}

Warshall

Ähnlich wie Floyd, aber er benutzt eine reflexive, transitive Hülle eines Graphen. Er verzichtet auf Werte, sondern beachtet nur, ob die Knoten miteinander verbunden sind. Das vereinfacht den Algorithmus ein wenig.

Algorithmus von Dijkstra

• Single-Source Best Path
• Dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen.
• Zeitkomplexität:

In Worten: Man berechnet die Kosten zwischen dem Vorgänger-Knoten und dem aktuellen Knoten und summiert dann immer. Der Pfad wird dann genommen, der am preiswertesten ist.

Prim-Algorithmus (Algorithmus von Prim)

• Dient der Berechnung eines minimalen Spannbaumes
• Immer die von einem Knoten abgehende kostengünstigste Kante nehmen
• Komplexität: O( | V | ²)