Сайт підготовки до олімпіади з інформатики

 (динамічне програмування)

Найкоротші шляхи

Нехай є n міст, пронумерованих числами від 1 до n. Для кожної пари міст із номерами і, j у таблиці a[і][j] зберігається ціле число - ціна прямого авіаквитка з міста i у місто j. Вважається, що рейси існують між будь-якими містами, a[і,і] = 0 при всіх і, a[і][j] може відрізнятися від a[j,і]. Найменшою вартістю проїзду з і в j вважається мінімально можлива сума цін квитків для маршрутів (у тому числі з пересадженнями), що ведуть з і в j. (Вона не перевершує a[і][j], але може бути менше).

У пропонованих нижче задачах потрібно знайти найменшу вартість проїзду для деяких пар міст при тих чи інших обмеженнях на масив a і на час роботи алгоритму.

Припустимо, що не існує  замкнутих маршрутів, для яких сума цін негативна. Передбачається, що ця умова (відсутність циклів з негативною сумою) виконана.

1) Знайти найменшу вартість проїзду з 1-го міста в усі інші .

Позначимо через Мінвар(1,s,к) найменшу вартість проїзду з 1 у s менш чим з k пересадженнями. Тоді виконується таке співвідношення:

Мінвар (1,s,k+1) = найменшому з чисел Мінвар(1,s,k) і

Мінвар(1,і,k) + a[і][s] (і=1..n)

Як відзначалося вище, шуканою відповіддю є Мінвар (1,і,n) для всіх і=1..n.

((0,20,3,4,5,6),

                                 (20,0,5,6,7,8),

                                 (3,5,0,6,7,8),

                                 (4,6,6,0,8,8),

                                 (5,7,7,8,0,9),

                                 (6,8,8,8,9,0));

1 2 -----20

1-3 ---- 3 , 3-2---- 5= 8

min(20,8)=8

флойд

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if a[i,k]+a[k,j]  a[i,j]:=a[i,k]+a[k,j];