4511
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:43, 17 июля 2014
, 17 июля 2014→Алгоритм Такаоки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
== Алгоритм Такаоки == | == Алгоритм Такаоки == | ||
Если стоимости | Если стоимости ребер ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния. | ||
Пусть 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 в ином случае. | Пусть 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 в ином случае. | ||