Der Dijkstra-Algorithmus · Der Dijkstra-Algorithmus Beispiel Betrachte folgenden Distanzgraphen...

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

aabbb ccc

dddeee fff

Inhalt von P entfernt besuchte Kanten Update-Operationen

(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

de f

1

7

3

3 68

1

13

a

a

bbb ccc

dddeee fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0)

(a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

de f

1

7

3

3 68

1

13

a

a

bbb ccc

dddeee fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e)

(b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b

c

a

d

e

f

1

7

3

3 68

1

13

a

ab

bb ccc

ddd

e

ee fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b

c

a

d

e

f

1

7

3

3 68

1

13

a

ab

b

b ccc

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7)

(b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b

c

a

d

e

f

1

7

3

3 68

1

13

a

abb

b

ccc

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1)

(b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b

c

a

d

e

f

1

7

3

3 68

1

13

a

abb

b

ccc

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c)

(c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

d

e

f

1

7

3

3 68

1

13

a

abb

b c

cc

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

d

e

f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7)

(c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

d

e

f

1

7

3

3 68

1

13

a

ab

b

b cc

c

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4)

(c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a

d

e

f

1

7

3

3 68

1

13

a

ab

b

b cc

c

ddde

e

e fff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f )

(d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b cc

c

d

dde

e

e

f

ff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12)

(e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

dee

e

f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7)

(e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

dee

e

f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f )

(f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e

f

ff

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12)

(f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e ff

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8)

(f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e ff

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d)

(d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

dde

e

e ff

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10)

(d , 10) − −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

dd

d

e

e

e f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10)

− −

Der Dijkstra-AlgorithmusBeispielBetrachte folgenden Distanzgraphen mit dem Startknoten a:

b c

a de f

1

7

3

3 68

1

13

a

ab

b

b c

c

c

d

d

de

e

e f

f

f

Inhalt von P entfernt besuchte Kanten Update-Operationen(a, 0) (a, 0) (a, b), (a, e) (b, 1), (e, 7)

(b, 1), (e, 7) (b, 1) (b, c) (c, 4)

(c, 4), (e, 7) (c, 4) (c, d), (c, e), (c, f ) (d , 12), (f , 10)

(e, 7), (f , 10), (d , 12) (e, 7) (e, f ) (f , 8)

(f , 8), (d , 12) (f , 8) (f , c), (f , d) (d , 10)

(d , 10) (d , 10) − −