---
tags: Assignments
---

# Blatt 08

|Kurs |Semester |Team |
|--- |--- |--- |
|Algorithmen und Datenstrukturen |SS 2020 |Carlo Mohl & Noah Nuebling |

---

## Aufgabe 1

### a)

- Modifikation 1: d wird mit 0 initialisiert
- Modifikation 2: Das < bei der Relaxierung wird zu einem >

### b)

1. Nach der Definition des Topologischen indexes, können von allen Knoten nur nur Kanten zu Knoten mit einem höheren topologischen Index ausgehen. Somit kann es auch nur Pfade zu Knoten mit höheren Topologischen Indexen geben.

2. Die Laufzeit des Sweep-Algorithmus wie in der Vorlesung auf Slide #16 Seite 51 gegeben ist unabhängig von dem Startknoten und vom Endknoten immer genau in Theta(n+m) (Da über jeden Knoten und über jede Kante genau einmal iteriert wird). Somit ist die Aussage komisch.

## Aufgabe 2

### a)

0.
           1  2  3  4  5  6  7  8
d =       [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
pre =     [-1,-1,-1,-1,-1,-1,-1,-1]

v1,v2.
           1  2  3  4  5  6  7  8
d =       [0, 4, ∞, ∞, ∞, ∞, ∞, ∞]
pre =     [-1, 1,-1,-1,-1,-1,-1,-1]

v1,v3.
           1  2  3  4  5  6  7  8
d =       [0, 4, 10, ∞, ∞, ∞, ∞, ∞]
pre =     [-1, 1, 1,-1,-1,-1,-1,-1]

v1,v4.
           1  2  3  4  5  6  7  8
d =       [0, 4, 10, 14, ∞, ∞, ∞, ∞]
pre =     [-1, 1, 1, 1,-1,-1,-1,-1]

v2,v3.
           1  2  3  4  5  6  7  8
d =       [0, 4, 7, 14, ∞, ∞, ∞, ∞]
pre =     [-1, 1, 2, 1,-1,-1,-1,-1]

v3,v5
           1  2  3  4  5  6  7  8
d =       [0, 4, 7, 14, 9, ∞, ∞, ∞]
pre =     [-1, 1, 2, 1, 3,-1,-1,-1]

v4,v6
           1  2  3  4   5  6  7  8
d =       [0, 4, 7, 14, 9, 5, ∞, ∞]
pre =     [-1, 1, 2, 1, 3, 4,-1,-1]

v4,v8
           1  2  3  4   5  6  7  8
d =       [0, 4, 7, 14, 9, 5, ∞, 19]
pre =     [-1, 1, 2, 1, 3, 4,-1, 4]

v5,v7
           1  2  3  4   5  6  7  8
d =       [0, 4, 7, 14, 9, 5, 10, 19]
pre =     [-1, 1, 2, 1, 3, 4, 5, 4]

v6,v3
           1  2  3  4   5  6  7  8
d =       [0, 4, 6, 14, 9, 5, 10, 19]
pre =     [-1, 1, 6, 1, 3, 4, 5, 4]

v6,v5
nichts verändert sich

v7,v8
           1  2  3  4   5  6  7  8
d =       [0, 4, 6, 14, 9, 5, 10, 8]
pre =     [-1, 1, 6, 1, 3, 4, 5, 7]

v8,v6
nichts verändert sich



v1,v2
nichts verändert sich

v1,v3
nichts verändert sich

v1,v4
nichts verändert sich

v2,v3
nichts verändert sich

v3,v5
           1  2  3  4   5  6  7  8
d =       [0, 4, 6, 14, 8, 5, 10, 8]
pre =     [-1, 1, 6, 1, 3, 4, 5, 7]

v4,v6
nichts verändert sich

v4,v8
nichts verändert sich

v5,v7
nichts verändert sich

v6,v3
nichts verändert sich

v6,v5
nichts verändert sich

v7,v8
nichts verändert sich

v8,v6
nichts verändert sich


...

### b)

Jede Spalte steht für eine Kante, die Kanten sind topologisch sortiert.
Jede Zeile steht für eine Runde. Jede Runde enthält also das abarbeiten jeder Kante.

Die Tabelle wird Zeile für Zeile von links nach rechts ausgefüllt.
Die Spalte des Startknotens ist immer 0 und alle Spalten links davon sind -1.
Für alle Knoten w die wir in Spalten rechts des Startknotens finden schauen wir nach links auf die Knoten die über Eingehende Kanten mit dem jetzigen Knoten verbunden sind und nennen diese v.
Wenn die Summe des Wertes in der Spalte für v und des Gewichtes der Kante zwischen v und w kleiner ist als der Wert von w aus der vorherigen (überliegenden) Zeile, dann schreiben wir die Summe in die Zelle, ansonsten schreiben wir den Wert aus der überliegenden Zeile.

In der letzten Zeile stehen nach dem Ausfüllen die Kosten der kürzesten Pfade.

v macht keinen Sinn
(Wenn wir nachvollziehen, an welchen Stellen wir nicht den Wert aus der Überliegenden Zeile übernehmen, können wir den kürzesten Weg hearusfinden.)

## Aufgabe 3

### a)

Dass alle Pfade in einem BFS Baum, wie in der Vorlesung gezeigt bei ungewichteten Graphen minial sind, müssen sie auch für alle GRaphen in denen alle Kanten gleich gewichtet sind minimal sein.

### b)

Für jede Kante auf dem minimalen Pfad wird 3 dazu addiert. Insgesamt wird also 3k dazu addiert.

### c)
Falsch. Gegenbeispiel, betrachte Graph mit V:={S,A,Z,B,C} u E:={((S,A)3),((A,Z)1),((S,B)1),((B,C)1),((C,Z)2)}, wobei ((x,y)z) x u. y jeweils Knoten beschreiben und z das Kantengewicht zwischen den Knoten.

### d)

Wahr, da die Vorletzte Kante der beiden Pfade im Pfad mit der größeren letzten Kante kleiner sein muss.

### e)

Falsch.
Der Bellman-Ford Algorithmus beachtet Kantengewichte nicht.

## Aufgabe 4

### a)

Da es in kürzesten Pfaden keine Kreise geben kann, ist jede Kante höchstens einmal in einem kürzesten Pfad enthalten. Somit ist die Summe aller Kantengewichte eine valide obere Schranke.

### b)

Wir legen ein Array von Knoten an.

Um die Priorität eines Knotens v zu bestimmen führen wir Counting Sort auf dem Array aus. Die Anzahl der Vorkommnisse des Knotens v ist gleich der Priorität von v. (`O(n+k)` - k und n sind glaub ich beides gleich der Anzahl der Knoten im Graphen. Also insgesamt O(Anzahl Knoten))

Bei insert(v)/decreaseKey(v) eines Knotens v mit der Priorität x, bestimmen wir zunuachst die bisherige Priorität p von v (mit Counting Sort wie oben beschrieben), dann fügen wir den Knoten `x - p` mal in das Array ein / entfernen den Wert v `x - p` mal aus dem Array. Die Laufzeit ist also in O(Anzahl Knoten).

Bei extractMin() lassen wir zunächst Counting Sort laufen, und dann lassen suchen wir das minimum, die Laufzeit hier ist auch in O(n)

Die Laufzei für Dijkstra ist also in O((m+n)*n)