TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 320

Aus VoWi
Zur Navigation springen Zur Suche springen

Im nachstehenden bewerteten Graphen bestimme man den Entfernungsbaum bezüglich des Knotens v_0.

Bsp212 1.png

Lösungsvorschlag von mnemetz[Bearbeiten]

Entfernungsbaum[Bearbeiten]

Entfernungsbäume werden in gewichteten Graphen erstellt, wenn von einem Startpunkt aus in mehreren Zwischenschritten klar sein soll, wie viel der Weg zu diesem und jenen Punkt insgesamt "kostet".

Um einen Entfernungsbaum zu erstellen geht man wie folgt vor:

  1. Die Wurzel ist die Ecke s (Startpunkt)
  2. Ecken des Baumes sind die von s aus erreichbaren Ecken des Graphen
  3. Als Kanten werden die kürzesten Wege von der Ecke s zur entsprechenden Ecke eingezeichnet. Schon vorhandene kürzeste Wege werden benutzt
  4. Die Kanten werden mit den Abständen zwischen ihren Ecken bewertet.

Man kann aus einem Entfernungsbaum die Abstände zur Ecke s sofort ablesen. Dazu geht man einfach ”den Baum nach unten” bis zur interessierenden Ecke und addiert die Bewertungen. Allerdings sind Entfernungsbäume nicht eindeutig (weil es mehrere kürzeste Wege geben kann).

Anders hätte man fragen können: Gesucht sei der minimal spannende Baum!

[Anmerkung von David Mihola: Das mit dem minimal spannenden Baum stimmt nicht. Der minimale spannende Baum muss nicht dieselben Kanten beinhalten wie ein Entfernungsbaum. In diesem konkreten Fall müsste der minimal spannende Baum statt der Kante v1-v3 die Kante v2-v3 enthalten, da 3 weniger ist als 7. (Vgl. Kruskal-Algorithmus)]

Entfernungsbaum mit Tabelle erstellen[Bearbeiten]

Weg v_0 \rightarrow v_3 - kürzester Weg zwischen diesen Punkten mit dem Dikstra-Algorithmus herausfinden!

Anmerkung

Iteration

v_0 v_1 v_2 v_5 v_4 v_3 Auswahl Vorgänger
1 1 \infty 3 \infty \infty v_1 v_0
2 9 2 5 8 v_3 v_1

Halten wir nun den kürzesten Weg von v_0 nach v_3 mit \mathbf{v_0 \rightarrow v_1 \rightarrow v_3} fest!

Anmerkung: Das Ergebnis stimmt zwar, aber ich denke das der Algorythmus zu früh "abgebrochen" wurde. BTW fehlt bei der 1ten Iteration die Verbindung von v_0 \rightarrow v_4 mit dem Gewicht 5

Weg v_0 \rightarrow v_1 - kürzester Weg zwischen diesen Punkten mit dem Dikstra-Algorithmus herausfinden!

Anmerkung

Iteration

v_0 v_1 v_2 v_5 v_4 v_3 Auswahl Vorgänger
1 1 3 \infty \infty \infty v_1 v_0

Halten wir nun den kürzesten Weg von v_0 nach v_1 mit \mathbf{v_0 \rightarrow v_1} fest! (führt schon entlang eines Weges nach v_3!).

Weg v_0 \rightarrow v_2 - kürzester Weg zwischen diesen Punkten mit dem Dikstra-Algorithmus herausfinden!

Anmerkung

Iteration

v_0 v_1 v_2 v_5 v_4 v_3 Auswahl Vorgänger
1 1 3 \infty \infty \infty v_1 v_0
2 9 2 5 8 v_5 v_1
3 4 v_4 v_5
4 7 v_2 v_4
5 9 2 5 8 v_4 v_1
6 8 v_2 v_4
7 9 v_2 v_1

Halten wir nun den kürzesten Weg von v_0 nach v_2 mit \mathbf{v_0 \rightarrow v_1 \rightarrow v_4} fest!

Weg v_0 \rightarrow v_5 - kürzester Weg zwischen diesen Punkten mit dem Dikstra-Algorithmus herausfinden!

Anmerkung

Iteration

v_0 v_1 v_2 v_5 v_4 v_3 Auswahl Vorgänger
1 1 3 \infty \infty \infty v_1 v_0
2 2 v_5 v_1

Halten wir nun den kürzesten Weg von v_0 nach v_5 mit \mathbf{v_0 \rightarrow v_1 \rightarrow v_5} fest!

Weg v_0 \rightarrow v_4 - kürzester Weg zwischen diesen Punkten mit dem Dikstra-Algorithmus herausfinden!

Anmerkung

Iteration

v_0 v_1 v_2 v_5 v_4 v_3 Auswahl Vorgänger
1 1 3 \infty \infty \infty v_1 v_0
2 5 v_4 v_1
3 2 v_5 v_1
4 4 v_4 v_5

Halten wir nun den kürzesten Weg von v_0 nach v_4 mit \mathbf{v_0 \rightarrow v_1 \rightarrow v_5 \rightarrow v_4 } fest!

[Anmerkung von David Mihola: Ich weiß nicht genau, was hier passiert: Es müsste doch reichen, ein einziges Mal den Dijkstra-Algorithmus durchzuführen und zwar so lange, bis jeder Knoten einmal der Knoten mit der geringsten Total-Entfernung zum Startknoten war - dann hat man nämlich für jeden Knoten den minimalen Abstand zum Startknoten gefunden.]

Bsp212 neu.png

Gesamte Tabelle[Bearbeiten]

vo v1 v2 v3 v4 v5 Auswahl Vorgänger
0 - - - - - v0 -
1 - - 5 3 v1 v0
9 8 5 2 v5 v1
9 8 4 v4 v5
7 8 v2 v4
8 v3 v1

Webressourcen[Bearbeiten]