Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechnung kürzester Weg

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Berechnung kürzester Wege

Auf dieser Seite wird die Berechnung der kürzesten Wege behandelt.

Gegeben ist ein (Di-)Graph $G=(V,E,\gamma )$ mit einer Gewichtsfunktion: $\gamma :E\to \mathbb {N}$. Der Pfad durch G ist eine Liste von aneinanderstoßenden Kanten $P=\{(v_{1},v_{2}),(v_{2},v_{3}),...(v_{n-1},v_{n})\}\subseteq E$. Das Gewicht oder die Länge eines Pfades ist die Aufsummierung der einzelnen Kantengewichte. $w(P)=\sum _{i=1}^{n-1}\gamma ((v_{i},v_{i+1}))$. Die Distanz zweier Punkte d(u,v) ist das Gewicht des kürzesten Pfades von u nach v.

Es existieren verschiedene kürzeste Wege Probleme.

SPSP: Single pari shortest path

Eingabe: Graph G, Startknoten s, Endknoten t

Ausgabe: Distanz d(s,t)

SSSP: Single source shortest paths

Eingabe: Graph G, Startknoten s

Ausgabe: Distanzen d(s,v) für alle Knoten v

APSP: All-pairs shortest paths

Eingabe: Graph G

Ausgabe: Distanzen d(v,w) für alle Knoten v,w

Auf den nächsten Seiten lernen wir zwei Algorithmen zum Berechnen des kürzesten Weges kennen.