Der Floyd-Warshall-Algorithmus

Preview:

Citation preview

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d0 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 ∞ 3 1 ∞

d1 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d0 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 ∞ 3 1 ∞

d1 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d0 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 ∞ 3 1 ∞

d1 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d0 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 ∞ 3 1 ∞

d1 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 3 1 ∞

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d0 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 ∞ 3 1 ∞

d1 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d1 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

d2 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

d2 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

d2 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ ∞

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 ∞

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

d3 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

d3 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

d3 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 4 ∞

5 10 3 1

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d2 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ ∞ 4 ∞ ∞

5 10 12 3 1 9

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d4 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d4 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d4 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d3 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d5 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d5 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d5 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d5 1 2 3 4 5

1

2

3

4

5

Der Floyd-Warshall-Algorithmus

Beispiel

Als nächstes betrachten wir folgenden Digraphen:

1

2

5 4

32

−2

10

−3

1

43

d4 1 2 3 4 5

1 ∞ 2 ∞ ∞ −1

2 ∞ ∞ ∞ ∞ −3

3 ∞ −2 ∞ ∞ −5

4 ∞ 2 4 ∞ −1

5 10 1 3 1 −2

d5 1 2 3 4 5

1 9 0 2 0 −3

2 7 −2 0 −2 −5

3 5 −4 −2 −4 −7

4 9 0 2 0 −3

5 8 −1 1 −1 −4

Recommended