Виконано формалізацію алгоритму Данцига пошуку найкоротших шляхів у зв'язному орієнтованому графі з використанням математичного апарата модифікованих систем алгоритмічних алгебр В.М. Глушкова. Запропоновано концепції розпаралелювання для архітектур зі спільною пам'яттю, що ґрунтуються на мінімізації витрат на синхронізацію та паралельну обробку даних. Проведено трансформацію алгоритму, отримано набір паралельних схем та виконано їх порівняльний аналіз.