Ітерація алгоритму

Кожну ітерацію алгоритму можна розділити на три послідовні кроки:

1. Пошук найкоротших шляхів з вершини до . Шлях можна розбити на дві частини: від до деякої проміжної вершини ( ) та від до ( ). Тоді .

2. Пошук найкоротших шляхів з вершин до . Шлях можна розбити на дві частини: від до деякої проміжної вершини ( ) та від до ( ). Тоді .

3. Пошук найкоротших шляхів з вершин до з урахуванням наявності нової вершини . Шлях можна розбити на дві частини: від до вершини ( ) та від до ( ). Тоді .

Останній крок рекурентної процедури дає матрицю , яка, власне, і буде матрицею найкоротших шляхів графа.