Для всіх інших пар вершин вважаємо dij=? (шляху покищо немає), а kij=0(немає наступної вершини).

На початку в таблиці враховані тільки шлахи рівні 1. На кожному кроці алгор. обходимо по черзі всі вітки з індексами і та j та порівнюємо відстані і та j з сумами di1+d1j, di2+d2j, …, din+dnj, тобто з найкоротшими вже отриманими шляхами з vi у vj через v1, v2 ,…,vn. Якщо найменша з цих сум менша від j то замінюємо dij на цю суму і замість kij пишемо вершину kil, де dil+dlj- найменша. Якщо при обході всієї таблиці зробимо хоча б одну зміну, повторюємо крок знову. Якщо потрібно знайти найкоротший шлях тільки між двома вершинами u та застосовують алгоритм Дійкстри. Для нього у всіх вершинах графа ставлять позначки двох типів – тимчасові і постійні. Кожна позначка має вигляд (d,k), де d- вершини w, d- найкоротший вже отриманий шлях з u в v, k- вершина яка передує w в цьому шляху. На початку постійну позначку (0;0) ставимо тільки у вершині u. В усіх інших верщинах ставимо тимчасові позначки (?,0). В кожний момент навколо вершини, в якій останньою поставлено постійну позначку, розглядаємо всі сусідні вершини з тимчасовими позначками. Якщо остання постійна позначка – у вершині ,а у суідній з нею вершині vj- тимчасова позначка, то порівнюємо числа і di+lij, де lij- довжина з і в j. Якщо сума виявляється меншою, замінюємо на неї dj ,і kj на в тій вершині, сусідній до i в якій тимчасова позначка dj є найменшою, робимо її постійною. Алгоритм зупиняється коли у вершині v ставимо постійну позначку. Алгоритм Дійкстри для однієї пари вершин вимагає набагато менше обчислень ніж алгоритм Флойда для всіх пар вершин, але застосовується алг. Дійкстри до всіх пар вершин приблизно в 2 довше ніж алг. Флойда.

6. Алгоритм Форда-Фалкерсона.

Означ.: Потоком в мережі G=(V,E) між вершинами s і t називають такий набір потоків по всіх ребрах графа, що для всіх вершин U, крім s і t маємо div(U,f)=0 (скільки у вершину втікає, стільки і витікає) і для кожного ребра(U,V) є Е маємо - тобто потік по кожному ребру невід’ємний і не перевищує максимальної пропускної здатності. При цьому, як правило, потоки тільки від s і тільки до t.( s- джерело потоку, t – його стік).

c(U,V) – пропускна здатність ребра;

f(U,V) – потік по даному ребру;

div(U,f) – різниця сум всіх потоків, які витікають з U і втікають в U. div(U,f)=;

Р – розріз.

Даний алгоритм випливає із теореми Форда-Фалкерсона:

Max w(f)=min c(f): максимум із пропускних здатностей розрізів між s і t.

Для довільної множини можна побудувати максимальний потік між s і t за допомогою рекурентного алгоритму.

Алгоритм Форда-Фалкерсона:

Починаємо з нульового потоку і намагаємося його збільшити. Нехай вже маємо деякий потік f між s і t. В кожній вершині ставимо мітку вигдяду , де величина, на яку можна збільшити потік з s в цю вершину, n –попередня вершина, через яку можна збільшити потік в дану вершину. Становимо “+”,якщо ребро іде від попередньої вершини до даної. Потік по ребру можна збільшити, та “-”, якщо від даної і попередньої вершини потік можна зменшити.

Позначки є 2-ох типів: тимчасові і постійні. На початку ставимо тимчасову позначку вигляду у вершині s. Вона означає. Що потік з s в s можна збільшувати необмежено і при цьому не потрібно проходити через жодну іншу вершину.

На кожному кроці обираємо одну з вершин з тимчасовою позначкою , яку робимо постійною.

Навколо цієї вершини V, в якій немає позначки або вона є тимчасовою. Якщо у V немає позначки й існує ребро (U,V), потік по якому немає макс. пропускної здатності, тобто <c(U,V), то у вершині V ставимо позначку , яка означає, що можна збільшити потік від s до V через вершину U. Якщо ж існує ребро (U,V) потік по якому не нульовий: , яка означає, що можна збільшити потік від s до U і одночасно зменшити зворотній потік від V до U, за рахунок чого зросте потік від s до V.

Якщо у вершині V вже є тимчасова позначка , то замінюємо її на нову тільки в тому випадку, коли нова величина або більше від попередньої .

Коли у вершину t ставимо постійну позначку, то відповідно до позначок збільшується потік від s до t, стираємо всі позначки і починаємо процес знову.

Якщо більше не можливо перетворити тимчасову позначку на постійну, то побудований потік вже є максимальний.

П-ад: - кольором виділено постійні позначки.

s | a | b | t

(1,s,+) | (2,s,+)

(1,s,+) | (2,s,+) | (1,a,+)

(1,s,+) | (2,s,+) | (1,a,+)

(2,s,+)

(2,b,+) | (2,s,+) | (1,b,+)

(2,b,+) | (2,s,+) | (2,a,+)

1)

(1,s,+) (2,s,+)

2) (2,b,+) (2,a,+)

(2,s,+)

3)

Отримали максимальний потік: w(f)=3.

7. Скінченні автомати.

Автоматом Мілі називають п’ятірку А, X, Y, f, g, яка складається з з

множини А станів автомата

вхідного алфавіту х і вихідного алфавіту у.

Функції переходів f: (A x x)>X і функції переходів (A x x)>У

Вважаємо, що автомат може перебувати