Алгоритм Беллмана-Форда
. Змістовна та формальна (математична) постановка завдання
алгоритм програма налагодження
Алгоритм Беллмана-Форда - алгоритм пошуку найкоротшого шляху в зваженому графі. За час O (| V | Ч | E |) алгоритм знаходить найкоротші шляхи від однієї вершини графа до всіх інших. На відміну від алгоритму Дейкстри, алгоритм Беллмана-Форда допускає ребра з негативним вагою. Запропоновано незалежно Річардом Беллманом і Лестером Фордом.
Граф, або неорієнтовані граф - це впорядкована пара lt; # 14 src= doc_zip2.jpg / gt;- Це непорожнє безліч lt; # 16 src= doc_zip3.jpg / gt; - це безліч пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами.
Рис. 1.1. Неорієнтовані граф.
(а значить і,, інакше воно було б Мультімножество lt; # 19 src= doc_zip7.jpg / gt; - порядком, число ребер - розміром графа.
Вершини і називаються кінцевими вершинами (або просто кінцями) ребра. Ребро, у свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми.
Два ребра називаються суміжними, якщо вони мають спільну кінцеву вершину.
Два ребра називаються кратними, якщо множини їх кінцевих вершин збігаються.
Ребро називається петлею, якщо його кінці збігаються, тобто.
Ступенем вершини називають кількість інцидентних їй ребер (при цьому петлі вважають двічі).
Вершина називається ізольованою, якщо вона не є кінцем ні для одного ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.
Орієнтований граф (скорочено орграф) - це впорядкована пара lt; # 21 src= doc_zip16.jpg / gt;,
для якої виконані наступні умови:
- це непорожнє безліч lt; # 16 src= doc_zip18.jpg / gt; - це безліч (впорядкованих) пар різних ребер, званих дугами або орієнтованими ребрами.
lt; # 21 src= doc_zip20.jpg / gt ;, де вершину називають початком, а - кінцем дуги. Можна сказати, що дуга веде від вершини до вершини.
Змішаний граф - це граф, в якому деякі ребра можуть бути орієнтованими, а деякі - неорієнтованими. Записується впорядкованої трійкою
,
де, і визначені так само, як вище.
Орієнтований і неорієнтовний графи є окремими випадками змішаного.
Граф називається ізоморфним графу, якщо існує біекція lt; # 18 src= doc_zip33.jpg / gt; з безлічі вершин графа в безліч вершин графа, що володіє наступною властивістю: якщо в графі є ребро з вершини у вершину, то в графі повинно бути ребро з вершини в вершину і навпаки - якщо в графі є ребро з вершини у вершину, то в графі повинно бути ребро з вершини у вершину. У разі орієнтованого графа lt; # 9 src= doc_zip48.jpg / gt; і є кінцями деякого ребра, то згідно з цим визначенням, послідовність є циклом. Щоб уникнути таких «вироджених» випадків, вводять такі поняття.
Шлях (або цикл) називають простим, якщо ребра в ньому не повторюються; елементарним, якщо він простий і вершини в ньому не повторюються. Нескладно бачити, що:
Всякий шлях, що з'єднує дві вершини, містить елементарний шлях, що з'єднує ті ж дві вершини.
Всякий простий Неелементарні шлях містить елементарний цикл.
Всякий простий цикл, що проходить через деяку вершину (або ребро), містить елементарний (під-) цикл, що проходить через ту ж вершину (або ребро).
Петля - елементарний цикл.
Бінарне відношення lt; # 9 src= doc_zip51.jpg / gt; в », є відношенням еквівалентності lt; # 14 src= doc_zip53.jpg / gt ;. Слово «максимальний» означає максимальний щодо включення, тобто не міститься в зв'язковому підграфі з великим числом елементів
Ребро графа називається мостом, якщо його видалення збільшує число компонент.
Таблиця 1.1. Позначення елементів
№Обозначеніе елементів математичної моделіНаіменованіе елементів математичної моделі1GГраф2Vнепустое безліч lt; # justify gt ;. Розробка алгоритму розв'язання задачі
Опишемо алгоритм по кроках:
Крок 0. Занумеруем всі вершини з G=(V, E), так що V={1, 2, ... p} і при цьому номер «1» має саме та вершина, з якої будуть знайдені найкоротші шляхи в усі інші вершини. Побудуємо, далі матрицю
=(mij), i, j=1, 2, ... p, поклавши
Крок 1. Близько першого рядка матриці M, ліворуч від матриці, поставимо числову позначку «0» і таку ж позначку проставимо над першим стовпцем матриці. Потім розглянемо позначену рядок зліва направо і щоразу, зустрічаючи клітку з числом, дода...
