Про підхід до розпаралелювання алгоритму Флойда-Уоршалла

Abstract

Виконано формалізацію алгоритму Флойда-Уоршалла з використанням математичного апарату систем алгоритмічних алгебр модифікованих. Запропоновано стратегії розпаралелювання та одержано паралельну регулярну схему алгоритму. Виконано низку еквівалентних перетворень і отримано спектр модифікованих схем алгоритму Флойда-Уоршалла.

Выполнена формализация алгоритма Флойда-Уоршалла с использованием математического аппарата систем алгоритмических алгебр модифицированных. Предложены стратегии распараллеливания и получена параллельная регулярная схема алгоритма. Выполнена цепь эквивалентных преобразований и получен спектр модифицированных схем алгоритма Флойда-Уоршалла.

Floyd-Warshall’s algorithm formalization is executed with the use of mathematical means of the systems of algorithmic algebras modified. Conversion strategies of basic algorithm into a parallel one are offered and the parallel regular chart of algorithm is obtained. The chain of equivalent transformations is executed and the spectrum of the modified charts of Floyd-Warshall’s algorithm is got.