Представлення графа у пам’яті

Інформація про граф зберігається у вигляді двох матриць. Перша з них – матриця суміжностей графа. Вона являє собою набір вхідних даних для алгоритму і є незмінною до кінця його роботи(доступ лише на читання). Друга матриця – матриця маршрутів. У комірці з координатами зберігається номер вершини, до якої необхідно перейти після -ої на шляху до . Таким чином, шлях розбивається на 2 частини: з до деякої проміжної вершини та з до . Якщо , необхідно пройти по відповідному ребру між вершинами. За допомогою цієї матриці в динамічному режимі розраховуються довжини найкоротших шляхів між довільними парами вершин. В остаточному варіанті одержана матриця і є результатом роботи алгоритму.