2015-07-14
540
Кожну ітерацію алгоритму можна розділити на три послідовні кроки:
1. Пошук найкоротших шляхів з вершини 
до 
. Шлях можна розбити на дві частини: від до деякої проміжної вершини 
(
) та від до 
(
). Тоді 
.
2. Пошук найкоротших шляхів з вершин 
до . Шлях можна розбити на дві частини: від до деякої проміжної вершини () та від до (
). Тоді 
.
3. Пошук найкоротших шляхів з вершин до з урахуванням наявності нової вершини . Шлях можна розбити на дві частини: від до вершини (
) та від до (
). Тоді 
.
Останній крок рекурентної процедури дає матрицю 
, яка, власне, і буде матрицею найкоротших шляхів графа.
