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

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

(1)