Моделювання транспортної мережі (стр. 4 из 5)

Крок 0. Призначаємо вузлові 15 постійну мітку [0, -].

Крок 1. З вузла 15 можна досягти вузлів 21 2 12. Обчислюємо мітки для цих вузлів, у результаті одержуємо наступну таблицю міток:

Вузол	Мітка	Статус мітки
15		Постійна
21	[512,15]	Тимчасова
2	[237,15]	Тимчасова

Серед вузлів 21, 2, 12, вузол 12 має найменше значення відстані (U12=172). Тому статус мітки цього вузла змінюється на «постійна».

Крок 2. З вузла 12 можна потрапити у вузли 2, 23, 22. Одержуємо наступний список вузлів.

Тимчасовий статус мітки [237,15] вузла 2 заміняється на постійний (U2=237).

Крок 3. З вузла 2 можна досягти вузлів 21, 22, 31. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Тимчасова
21	[370+512,2]=[882,2]	Тимчасова
22	[1009,12]	Тимчасова
22	[696+237,2]=[933,2]	Тимчасова
23	[810,12]	Тимчасова
31	[655+237,2]=[892,2]	Тимчасова

Тимчасовий статус мітки [512,15] вузла 21 заміняється на постійний (U21=512).

Крок 4. З вузла 21 можна досягти вузлів 31. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
22	[933,2]	Тимчасова
23	[810,12]	Тимчасова
31	[892,2]	Тимчасова
31	[512+289,21]= [801,21]	Тимчасова

Тимчасовий статус мітки [801,21] вузла 31 заміняється на постійний (U31=801).

Крок 5. З вузла 31 можна досягти вузлів 22, 38. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
31	[801,21]	Постійна
22	[933,2]	Тимчасова
22	[801+237,31]= [1038,31]	Тимчасова
23	[810,12]	Тимчасова
38	[801+197,31]= [992,31]	Тимчасова

Тимчасовий статус мітки [810,12] вузла 23 заміняється на постійний (U23=810).

Крок 6. З вузла 23 можна досягти вузла 22, 38, 3. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
31	[801,21]	Постійна
23	[810,12]	Постійна
22	[933,2]	Тимчасова
22	[810+535,23]= [1345,23]	Тимчасова
38	[992,31]	Тимчасова
38	[810+929,23]= [1739,23]	Тимчасова
3	[810+1045,23]= [1855,23]	Тимчасова

Тимчасовий статус мітки [933,2] вузла 22 заміняється на постійний (U22=933).

Крок 7. З вузла 22 можна досягти вузлів 38, 3. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
31	[801,21]	Постійна
23	[810,12]	Постійна
22	[933,2]	Постійна
38	[992,31]	Тимчасова
38	[933+427,22]= [1360,22]	Тимчасова
3	[1855,23]	Тимчасова
3	[933+938,22]= [1871,22]	Тимчасова

Тимчасовий статус мітки [992,31] вузла 38 заміняється на постійний (U38=992).

Крок 8. З вузла 38 можна досягти вузла 3. Після обчислення міток одержимо наступний їх список:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
31	[801,21]	Постійна
23	[810,12]	Постійна
22	[933,2]	Постійна
38	[992,31]	Постійна
3	[1855,23]	Тимчасова
3	[992+116,38]= [1108,38]	Тимчасова

На останньому кроці знайдено найкоротшу відстань для вузла 3 – [1108.38]. Таким чином статус мітки вузла 3 змінюється на постійний.

Кінцевий результат міток має такий вигляд:

Вузол	Мітка	Статус мітки
15		Постійна
12	[172,15]	Постійна
2	[237,15]	Постійна
21	[512,15]	Постійна
31	[801,21]	Постійна
23	[810,12]	Постійна
22	[933,2]	Постійна
38	[992,31]	Постійна
3	[1108,38]	Постійна

Найкоротший шлях між вузлом 15 і будь-яким іншим вузлом визначається починаючи з вузла призначення шляхом проходження їх у зворотному напрямку за допомогою інформації, представленої в постійних мітках. Найкоротший маршрут між вузлами 15 і 3 має таку послідовність вузлів: (3)→ [1108.38] →(38)→ [992.31] →(31)→ [801.21] →(21)→ (15).

Таким чином, одержуємо шлях загальною довжиною 1108 км.

4. Задача про максимальний потік (алгоритм Форда-Фалкерсона)

Рішення задачі складається з підготовчого етапу і кінцевого числа кроків, на кожнім з яких відбувається припустиме збільшення потоку. На підготовчому етапі формується матриця пропускних здатностей дуг мережі.

Таблиця 4.1. Матриця пропускних здатностей дуг мережі

	15	12	2	21	31	23	22	38	3
15	-	10	¹⁰	10^-
12	7	-	7			7	7
2	¹³	13	-	13	13		13
21	18⁺		18	-	18^-
31			22	22⁺	-		22	22^-
23		22				-	22	22	22
22		21	21		21	21	-	21	21
38					28⁺	28	28	-	28^-
3						7	7	7⁺	-

По табл. 4.1. знаходимо шлях l1=(15,21,31,38) зі станції 15 у 3 з позитивною пропускною здатністю. Елементи цього шляху

позначаємо знаком «мінус», а симетричні

– знаком «плюс». Визначаємо пропускну здатність знайденого шляху, що дорівнює найменшій з пропускних здатностей дуг: C1= min {10,18,22,28}=10.

Визначаються залишкові пропускні здатності дуг знайденого шляху і симетричних йому дуг. Для цього з елементів

табл. 4.1. віднімаємо

, а до елементів

додаємо

. У результаті одержимо нову табл. 4.2 зі зміненими пропускними здатностями.

Таблиця 4.2. Матриця пропускних здатностей дуг мережі