Алгоритм Данцига

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

Перенумеруємо всі вершини графа числами від до , де – розмірність графа, який віддзеркалює топологію мережі. Кожному ребру відповідає певний ваговий коефіцієнт. Якщо ребра немає, то значення коефіцієнта рівне нескінченності. Вихідними даними для алгоритму є матриця вагових коефіцієнтів. Ідея полягає в послідовному обчисленні за допомогою рекурентної процедури під матриць найкоротших шляхів зростаючої розмірності . Кожна така матриця, фактично, є матрицею найкоротших шляхів під графа з вершинами від до .

Деякі позначення:

– розмірність графа, який віддзеркалює топологію мережі;

– множина цілих чисел від до ;

– довжина ребра з вершини в ;

– довжина найкоротшого знайденого шляху з в ;

– шлях з вершини до через вершину ;

– предикат, значенням якого буде істина, якщо існує ребро з вершини в ;

– предикат, значенням якого буде істина, якщо існує шлях з вершини в ;

– кількість ребер на шляху з в ;

– встановлення шляху .