Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями

Задача поиска кратчайших путей между всеми парами (APSP) заключается в нахождении кратчайших путей между всеми парами вершин в ориентированном графе с дугами неотрицательной действительной стоимости. Основное внимание уделяется кратчайшим расстояниям между вершинами, поскольку кратчайшие пути могут быть найдены с незначительным возрастанием стоимости. Классические алгоритмы решают задачу нахождения кратчайших путей между всеми парами вершин за кубическое время – <math>O(n^3) \, </math>. Наша задача заключается в достижении меньшего времени исполнения алгоритма для графа с небольшими целочисленными стоимостями дуг.

Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги <math>(i, j) \in E\, </math> обозначается как <math>d_{ij}\, </math>. Матрица D размера <math>n \times n</math> содержит элемент <math>d_{ij}\, </math> в позиции (i, j). Для простоты предположим, что <math>d_{ij} > 0 \, </math> и <math>d_{ii} = 0 \, </math> для всех <math>i \ne j</math>. Если не существует дуги из i в j, положим <math>d_{ij} = \infty</math>. Стоимость, или расстояние, пути представляет собой сумму стоимостей всех дуг на пути. Длина пути равна количеству дуг на пути. Кратчайшее расстояние между вершинами i и j равняется минимальной стоимости среди всех путей, ведущих от i до j, и обозначается как <math>d_{ij}^*</math>. Пусть <math>D^* = {d_{ij}^*}</math>. Значение n называется размером матрицы.