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

(2) <math>c_{ij} = \bigvee_{k=1}^n a_{ik} \wedge b_{kj}</math>

В любом из трех случаев матрица C называется произведением, а процесс вычисления – умножением. Во всех трех случаях k пробегает весь диапазон (1, …, n}. Частичное произведение матриц A и В определяется для значений k из подмножества I множества V. Иными словами, частичное произведение получается при умножении вертикальной прямоугольной матрицы A(*, I), столбцы которой извлечены из матрицы A согласно множеству I, и горизонтальной прямоугольной матрицы B(I, *), полученной из B путем извлечения строк, соответствующих множеству I. Интуитивно множество I представляет собой множество контрольных точек k при переходе от i к j в графе.