|
Читайте также: |
В ряде задач интерес представляет только сам факт существования пути, длиной не меньше 1, от вершины i до вершины j. Для решения таких задач применяется алгоритм Уоршелла.
Предположим, что матрица стоимостей С совпадает с матрицей смежности для данного орграфа G, т.е. C[i, j] =1 только в том случае, если есть дуга 
, и C[i, j] =0, если такой дуги не существует. Требуется определить матрицу А такую, что А[i, j] =1 тогда и только тогда, когда существует путь от вершины i до вершины j длиной не менее 1 и А[i, j] =0 – в противном случае. Такую матрицу А часто называют транзитивным замыканием матрицы смежности.
На рис. 45 показано транзитивное замыкание матрицы смежности орграфа из рис. 43.
Рис. 45 – Транзитивное замыкание матрицы смежности
Транзитивное замыкание можно вычислить, применяя на к -ом шаге следующую формулу к булевой матрице А.
Эта формула устанавливает, что существует путь от вершины i до вершины j, проходящих через вершины с номерами, не превышающими k, только в следующих случаях.
1. Уже существует путь от вершины i до вершины j, который проходит через вершины с номерами, не превышающими к -1.
2. Существует путь от вершины i до вершины к, проходящий через вершины с номерами, не превышающими к-1, и путь от вершины к до вершины j, который проходит через вершины с номерами, не превышающими к -1.
Дата добавления: 2015-07-16; просмотров: 147 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Нахождение кратчайших путей между парами вершин | | | Нахождение центра ориентированного графа |