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