# TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 24

Modify Dijkstra's algorithm such that it finds a path whose longest edge is as short as possible and apply it to the first graph in exercise 16, starting at ${\displaystyle v_{0}}$.

Graph from exercise 16:

## Lösungsvorschlag

Instead of considering the weights for the path until a vertex, consider only the weights of the currently available edges.

 Iteration v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 Auswahl Vorgänger 0 0 ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ ${\displaystyle \infty }$ v0 1 1 ${\displaystyle \infty }$ ${\displaystyle \infty }$ 5 ${\displaystyle \infty }$ ${\displaystyle \infty }$ 5 ${\displaystyle \infty }$ 8 v1 v0 2 ${\displaystyle \infty }$ ${\displaystyle \infty }$ 4 ${\displaystyle \infty }$ 7 5 ${\displaystyle \infty }$ 1 v9 v1 3 3 ${\displaystyle \infty }$ 4 ${\displaystyle \infty }$ 7 1 ${\displaystyle \infty }$ v7 v9 4 1 ${\displaystyle \infty }$ 4 3 7 5 v2 v7 5 4 4 3 4 5 v5 v7 6 3 1 4 5 v4 v5 7 3 1 5 v6 v4 8 3 4 v3 v5 9 4 v8 v6