В поштовому зв’язку радіальні маршрути використовуються, в основному, як магістральні та регіональні маршрути, а в разі нестачі часу для проходження кільцевих маршрутів – також як окружні маршрути.
Задача формулюється так: заданий зв’язний зважений граф, вершини якого відповідають вузлам мережі перевезень пошти, ребра – шляхам, що з’єднують ці вузли, а ваги ребер – протяжностям відповідних шляхів. Знайти найкоротші шляхи, що з’єднують задану початкову вершину з рештою вершин графа.
Розв’язання задачі засновано на формуванні так званого рельєфу графа у виді ваг вершин графа, значення яких дорівнюють значенням протяжностей найкоротших шляхів між ними і початковою вершиною графа.
Початковій вершині Ві надається вага Рі = 0, решті вершин – нескінченні ваги Рj = ¥.
На кожному кроку формування рельєфу графа знаходиться раніше неперевірена вершина мінімальної ваги, відносно якої формуються ваги тих неперевірених вершин, що безпосередньо з’єднані з перевірною вершиною. Вага неперевіреної вершини замінюється вагою перевірної вершини, збільшеної на вагу ребра, що з’єднує зазначені вершини, якщо перша перевищує другу.
Разом з формуванням рельєфу формується інформація про значення ваги кожної вершини і про номер вершини, від якої ця вага отримана.
Найкоротші шляхи формуються як послідовності записів зазначеної інформації, прочитані в порядку, зворотному до їхнього формування.
Алгоритм формування рельєфу графа наведений на рис. 2.5.
Початок
 |
1. Присвоєння початковій вершині
ваги Рi = 0, присвоєння решті
вершин ваг Рj = 999
 | |||
 | |||
2. Вибір серед неперевірених вершин
графа вершини Вk мінімальної ваги
 | |||
 | |||
3. Обчислення ваги 
= lk + P(k,j)
чергової неперевіреної вершини
Bj графа, безпосередньо пов’язаної
з перевірною вершиною Bk
 |
Ні
4. < Рj
Так
5. Рj = , запис Bk
 |
6. Всі
вершини Bj, безпосередньо Ні
пов’язані з вершиною Bk,
перевірені
Так
7. Присвоєння перевірній вершині
Bk позначки “перевірена” (*)
 |
Ні 8. Перевірено
n - 1 вершин графа
 |
Так
Кінець
Рисунок 2.5. Алгоритм формування рельєфу графа
Алгоритм містить 8 блоків.
У блоці 1 створюється початковий рельєф графа. Початковій вершині Ві присвоюється мінімальна вага Рі = 0, решті вершин графа Bj (j = 1, 2, … n, j ¹ i) – нескінченні ваги Рj = ¥, які подаються як надмірні ваги Рj = 999.
У блоці 2 серед неперевірених вершин вибирається вершина Вk мінімальної ваги Рk.
У блоці 3 обчислюється вага 
= Рk + Р(k,j) чергової неперевіреної вершини Bj відносно перевірної вершини Bk, що безпосередньо пов’язана з вершиною Bj графа.
У блоці 4 обчислена вага порівнюється з вагою Рj вершини Bj. При < Рj виконується перехід до блоку 5, при ³ Рj – до блоку 6.
У блоці 5 вага Рj замінюється вагою , тобто значення ваги вершини Bj знижується, і запам’ятовується вершина Bk, від якої одержано значення ваги Рj.
У блоці 6 перевіряється, чи всі вершини Вj графа, безпосередньо пов’язані з перевірною вершиною Bk, перевірені. Якщо так – здійснюється перехід до блоку 7, якщо ні – повернення до блоку 3.
У блоці 7 перевірній вершині Bk присвоюється позначка “перевірена” (*) і вона виключається з подальшого розгляду.
У блоці 8 перевіряється кількість вершин графа, що вже перевірені. Якщо таких вершин менше n - 1 – здійснюється повернення до блоку 2, і процес формування рельєфу графа повторюється, якщо їх n - 1 – рельєф графа сформований і робота алгоритму закінчується.
Алгоритм формування найкоротших шляхів за сформованим рельєфом графа наведено на рис. 2.6.
Алгоритм містить 5 блоків.
У блоці 1 фіксується поточна перевірна вершина Bl = Bj (j = 1, 2, … n,
j ¹ i).
У блоці 2 виконується зчитування рядка l таблиці рельєфу графа.
У блоці 3 фіксується значення номера попередньої вершини Bk графа та ваги Рl.
У блоці 4 значення l замінюється значенням k, тобто поточна вершина Bl замінюється поточною вершиною Bk графа.
У блоці 5 порівнюються значення l і i. При l ¹ i виконується повернення до блоку 2 і формування шляху між вершинами Bi та Bj графа продовжується. При l = i шлях між вершинами Bi та Bj графа сформований і робота алгоритму закінчується.
Початок
 |
1. l = j (j = 1, 2 …, n, j ¹ i)
 | |||
 | |||
2. Зчитування рядка l таблиці
рельєфу графа
 |
3. Запис номера попередньої
вершини Bk графа і ваги Pl
 |
4. l = k
 |
Ні 5. l = i
Так
Кінець
Рисунок 2.6. Алгоритм формування найкоротших шляхів
Послідовність кроків формування рельєфу графа рис. 2.3 відносно вершини 4 наведено в табл. 2.3 … 2.10 (Bi – будь-яка вершина, Рi – вага вершини Bi, * - позначка вершини “перевірена”, Bk – вершина, від якої одержана вага Рi).
|
|
|
| Крок 0: початковий | Крок 1: Рi = 0, Bi = 4 | Крок 2: Рi = 2, Bi = 3 | |||||||||
| Bi | * | Рi | Bk | Bi | * | Рi | Bk | Bi | * | Рi | Bk |
| * | |||||||||||
| * | * | ||||||||||
|
|
|
| Крок 3: Рi = 3, Bi = 1 | Крок 4: Рi = 3, Bi = 7 | Крок 5: Рi = 4, Bi = 6 | |||||||||
| Bi | * | Рi | Bk | Bi | * | Рi | Bk | Bi | * | Рi | Bk |
| * | * | * | |||||||||
| * | * | * | |||||||||
| * | * | * | |||||||||
| * | |||||||||||
| * | * | ||||||||||
|
|
|
Сформовані найкоротші шляхи між вершиною 4 та рештою вершин графа наведено у табл. 2.11 (в дужках зазначені протяжності відповідних шляхів або їх частин)
|
| 4 (0) – 3 (2) – 1 (3) |
| 4 (0) – 3 (2) – 1 (3) – 2 (7) |
| 4 (0) – 3 (2) |
| 4 (0) – 6 (4) – 8 (6) – 5 (9) |
| 4 (0) – 6 (4) |
| 4 (0) – 7 (3) |
| 4 (0) – 6 (4) – 8 (6) |
Наведені алгоритми формування рельєфу графа (рис. 2.5) і формування найкоротших шляхів за сформованим рельєфом графа (рис. 2.6) можуть бути використані також для формування шляхів, найкоротших за числом проміжних вершин.
У задачах поштового зв’язку такі шляхи використовуються для перевезень важкої (посилочної) пошти з метою скорочення витрат, пов’язаних з її перевантаженням у транзитних вузлах.
Для одержання зазначених шляхів достатньо прийняти ваги усіх ребер графа рівними одиниці.
У табл. 2.12 … 2.18 наведена послідовність кроків формування рельєфу графа рис. 2.3 відносно вершини 4 за умови рівності ваг усіх його ребер одиниці (позначення – такі ж самі, що в табл. 2.3 … 2.10).
|
|
|
| Крок 0: початковий | Крок 1: Рi = 0, Bi = 4 | Крок 2: Рi = 2, Bi = 3 | |||||||||
| Bi | * | Рi | Bk | Bi | * | Рi | Bk | Bi | * | Рi | Bk |
| * | |||||||||||
| * | * | ||||||||||
|
|
|
| Крок 3: Рi = 3, Bi = 1 | Крок 4: Рi = 3, Bi = 7 | Крок 5: Рi = 4, Bi = 6 | |||||||||
| Bi | * | Рi | Bk | Bi | * | Рi | Bk | Bi | * | Рi | Bk |
| * | * | * | |||||||||
| * | * | * | |||||||||
| * | * | * | |||||||||
| * | * | ||||||||||
| * | |||||||||||
 |
Оскільки на кроці 6 всі вершини отримали ваги, формування рельєфу закінчується.
У табл. 2.19 наведено найкоротші за числом проміжних вершин шляхи між вершиною 4 та рештою вершин графа.
|
| 4 – 1 |
| 4 – 1 – 2 |
| 4 – 3 |
| 4 – 1 – 2 – 5 |
| 4 – 6 |
| 4 – 7 |
| 4 – 6 – 8 |
