Реферат Розробка системи завдань (алгоритми-програми) з дискретної математики

лад (для малюнка). R (1) = {1} U {2,5} U {1,6} U {2,5,4} U {1,6,7} = {1,2,4,5,6,7}

Виконуючи ці дії для кожної вершини графа, ми отримуємо матрицю досяжними R.

Найкоротші шляху. Алгоритм Дейкстри

Дано. Орієнтований граф G = , s - вершина джерело; матриця суміжності A (A: array [1 .. n, 1 .. n] of integer); для будь-яких u, v € V вага дуги ненегативний (А [u, v]> = 0). Результат. Масив найкоротших відстаней - D.

У даному алгоритмі формується безліч вершин Т, для яких ще не обчислена оцінка відстань і, це головне, мінімальне значення в D по безлічі вершин, що належать Т, вважається остаточною оцінкою для вершини, на якій досягається цей мінімум. З точки зору здорового глузду цей факт досить очевидний. Інший "захід" в цю вершину можливий по шляху, який містить більшу кількість дуг, а так як ваги невід'ємні, то й оцінка шляху буде більше. br/>

Приклад

Його матриця суміжності:

в€ћ 3 липня в€ћ в€ћ в€ћ

1 в€ћ 2 в€ћ в€ћ 1

А = в€ћ 1 в€ћ 4 квітня в€ћ

в€ћ в€ћ в€ћ в€ћ 1 Травня

в€ћ в€ћ 1 в€ћ в€ћ 3

в€ћ в€ћ в€ћ 2 в€ћ в€ћ

В 

У таблиці наведена послідовність кроків (ітерацій) роботи алгоритму. На першому кроці мінімальне значення D досягається на другий вершині. Вона виключається з безлічі Т, і поліпшення оцінки до решти вершин (3,4,5,6) шукається не по всіх вершин, а тільки від другий.

№ ітерації

D [1]

D [2]

D [31

D [4]

D [5]

D [6]

T

1

0

3

7

в€ћ

в€ћ

в€ћ

[2,3,4,5,6]

2

0

3

5

в€ћ

11

4

[3,4,5,6]

3

0

3

5

6

в€ћ

4

[3,4,5]

4

0

3

5