Рішення задачі на графі без негативних циклів
Вирішимо поставлене завдання на графі, в якому свідомо немає негативних циклів.
Для знаходження найкоротших шляхів від однієї вершини до всіх інших, скористаємося методом динамічного програмування. Побудуємо матрицю Aij, елементи якої будуть позначати наступне: Aij - це довжина найкоротшого шляху з s у i, що містить не більше j ребер.
Шлях, що містить 0 ребер, існує тільки до вершини s. Таким чином, Ai0 дорівнює 0 при i = s, і плюс нескінченності в іншому випадку.
Тепер розглянемо всі шляхи з s в i, що містять рівно j ребер. Кожен такий шлях є шлях з j - 1 ребра, до якого додано останнє ребро. Якщо про шляхи довжини j - 1 всі дані вже підраховано, то визначити j-й стовпець матриці не складає труднощів.
Граф з негативним циклом
Алгорітм Беллмана - Форда дозволяє дуже просто визначити, чи існує в графі G негативний цикл, досяжний з вершини s. Досить зробити зовнішню ітерацію циклу не | V | - 1, a рівно | V | разів. Якщо при виконанні останньої ітерації довжина найкоротшого шляху до будь-якої вершини строго зменшилася, то в графі є негативний цикл, досяжний з s. На основі цього можна запропонувати наступну оптимізацію. Можна відстежувати зміни в графі і, як тільки вони закінчаться, подальші ітерації будуть безглузді. Значить можна зробити вихід з циклу.
2.3 Алгоритм пошуку A*
Алгоритм пошуку А* («А зірочка» або англ. «A star») — належить до евристичних алгоритмів пошуку. Використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер. Описаний 1968