start_v прирівнюється нулю. В
Рисунок 8 - Заповнення масиву
На малюнку 9 реалізований, безпосередньо алгоритм Беллмана-Форда. Тут rez [mRast [ j ]. from ] - довжина шляху з початкової вершини до вершини, від якої починається поточна дуга, mRast [ j ]. length - довжина поточної дуги, rez [mRast [ j ]. to ] - поточний найкоротша відстань з start_v до j -ої вершини.
В
Рисунок 9 - Алгоритм Беллмана-Форда
В останній частині псевдокоду, малюнок 10, здійснюється виведення найкоротших відстаней, при цьому, у випадку якщо rez [i] = 100000 шлях до j -ої вершини не визначений.
В
Рисунок 10 - Висновок найкоротших відстаней
3. Аналіз трудомісткості зростання функції
Час виконання програми за алгоритмом Флойда состовляет O ( n ^ 3 ) , оскільки в ній немає практично нічого, окрім 3 вкладених один в одного циклів.
Найкращим випадком для алгоритму стане граф в якому всього немає поліпшення шляху, тобто вводиться матриця відстаней не зміниться після виконання програми. У цьому випадку час виконання програми складе O ( n ^ 3 ) .
Найгіршим випадком для алгоритму стане граф з негативним циклом. Якщо в графі є цикли негативного ваги, то формально алгоритм Флойда до такого графу непридатний. Але насправді алгоритм коректно спрацює для всіх пар, шляху між якими ніколи не проходять через цикл негативної вартості, а для інших ми отримаємо якісь числа, можливо сильно негативні. Алгоритм можна навчити виводити для таких пар якесь значення, відповідне - ? .
В середньому випадку алгоритм не матиме негативних циклів і поліпшить майже всі шляхи. Таким чином він не перевищить an ^ 3 + bn ^ 2 + cn + d операцій.
