Networks2012-04-Routing

Алгоритм Дэйкстры

O Альтернативное название SPF (Shortest Path First)

O Основная идея – на каждом шаге выбор любого кратчайшего пути

Ицыксон В.М. ТКС © 2012

31

Алгоритм Дэйкстра

2	8	4

4	2

1	2	15	3	6

3	6
	7
3	5

Ицыксон В.М. ТКС © 2012

32

Алгоритм Дэйкстры

O P - множество помеченных вершин – вершин, для которых найден начальный маршрут

O Si – текущая оценка пути от 1-ой до 1-ой O m – номер текущего шага

Ицыксон В.М. ТКС © 2012

33

Алгоритм Дэйкстры

O Шаг 1. Начальные условия

O Множество P: P={1}

O Оценка пути:

O S1 := 0

O Si := r1,I

O m = 1

O Шаг 2.

O Sn := minj Sj

O P := P {n}

O Для всех i P:

O Si := min (Si, Sn + rn,i)

O m := m+1

O Шаг 3.

O Если m = N -> выход

O Иначе – переход к шагу 2

Ицыксон В.М. ТКС © 2012

34

Алгоритм Дэйкстры. Шаг 1

6		∞
2	8	4

6	2

0

1	2	4	3	6 ∞

3		6
		7
3		5
	3	∞

P={1}

Ицыксон В.М. ТКС © 2012

35

Алгоритм Дэйкстры. Шаг 2

6 5		∞ ∞
2	8	4

6	2

0

1	2	4	3	6	∞
					∞
	3	7		6
	3		5
		3		∞ 10

P={1, 3}

Ицыксон В.М. ТКС © 2012

36

Алгоритм Дэйкстры. Шаг 3

6 5		∞ ∞ 13
2	8	4

6	2

0

1	2	4	3	6	∞
					∞
					∞
	3	7		6
	3		5
		3		∞ 10 9

P={1, 3, 2}

Ицыксон В.М. ТКС © 2012

37

Алгоритм Дэйкстры. Шаг 4

6 5

2 8

6

0

1	2	4

3

7

3

3

P={1, 3, 2, 5}

∞ 14 13 12

4

2

3
		6	∞
			∞
			∞
	6		15

5

∞10 9

Ицыксон В.М. ТКС © 2012

38

Алгоритм Дэйкстры. Шаг 5

6 5

2 8

6

0

1	2	4

3

7

3

3

P={1, 3, 2, 5, 4}

∞ 14 13 12

4

2

3		6	∞
			∞
			∞
	6		15
			14

5

∞10 9

Ицыксон В.М. ТКС © 2012

39

Алгоритм Дэйкстры. Шаг 6

6 5

2 8

6

0

1	2	4

3

7

3

3

P={1, 3, 2, 5, 4, 6}

∞ 14 13 12

4

2

3		6	∞
			∞
			∞
	6		15
			14

5

∞10 9

Ицыксон В.М. ТКС © 2012

40