4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 13:29, 23 января 2012
, 23 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 39: | Строка 39: | ||
Пусть C' = A' B' – результат обычного матричного произведения, а C = A × B – результат произведения матриц расстояния. Тогда верно следующее: | Пусть C' = A' B' – результат обычного матричного произведения, а C = A × B – результат произведения матриц расстояния. Тогда верно следующее: | ||
<math>c'_{ij} = \sum_{k=1}^m (m + 1)^{2M - (a_{ik} + b_{kj})}</math>, <math>c_{ij} = 2M - \mathcal{b} log_{m + 1} c'_{ij} \mathcal{c}</math> | |||
Такое произведение матриц расстояния называется произведением (n, m)-Романи. Ранее мы имели дело с умножением квадратных матриц, или произведением (n, n)-Романи. В следующем разделе будет рассмотрен случай для m < n. | Такое произведение матриц расстояния называется произведением (n, m)-Романи. Ранее мы имели дело с умножением квадратных матриц, или произведением (n, n)-Романи. В следующем разделе будет рассмотрен случай для m < n. | ||