4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 13:22, 23 января 2012
, 23 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 34: | Строка 34: | ||
Если стоимости дуг ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния. | Если стоимости дуг ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния. | ||
Пусть A и B – матрицы расстояния формата (n, m) и (m, n), соответственно, элементы которых ограничены числом M либо равны бесконечности. Пусть диагональные элементы равны 0. Преобразуем матрицы A и B в A' и B', где a'ij = (m + | |||
Пусть A и B – матрицы расстояния формата (n, m) и (m, n), соответственно, элементы которых ограничены числом M либо равны бесконечности. Пусть диагональные элементы равны 0. Преобразуем матрицы A и B в A' и B', где <math>a'_{ij} = (m + 1)^{M - a_{ij}}</math>, если <math>a_{ij} \ne \infty \, </math>, и 0 в противном случае, а <math>b'_{ij} =(m + 1)^{M - b_{ij}}</math>, если <math>b_{ij} \ne \infty \, </math>, и 0 в ином случае. | |||
Пусть C' = A' B' – результат обычного матричного произведения, а C = A × B – результат произведения матриц расстояния. Тогда верно следующее: | Пусть C' = A' B' – результат обычного матричного произведения, а C = A × B – результат произведения матриц расстояния. Тогда верно следующее: | ||