![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Категории: АстрономияБиология География Другие языки Интернет Информатика История Культура Литература Логика Математика Медицина Механика Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Транспорт Физика Философия Финансы Химия Экология Экономика Электроника |
Построение деревьев кратчайших путейДО 4 БАЛЛОВ ЗА КОНСПЕКТ Алгоритм Флойда определения кратчайших путей между всеми парами вершин данного графа Если в графе р вершин, требуется отыскать Произвольно перенумеруем вершины графа числами от 1 до р. Обозначим через Числа Числа Опишем переход от чисел Разрешение вершине с номером
Если в графе р вершин, то требуется р раз вычислять Количество вычислений можно сократить. При переходе от матрицы Dk к матрице Dk+1 не нужно пересчитывать строку и столбец с номером Подобным образом Попросту говоря, если вершина с номером Пример. Определим длины кратчайших путей между всеми парами вершин графа, изображенного на рис. 9. Перейдем от матрицы D0 к матрице D1. Первую строку и первый столбец матрицы D1 переносим из матрицы D0.
Кроме того, В матрице D0 первом столбце и четвертой строке также стоит бесконечность, из четвертой вершины в вершину 1 пути нет, невозможно найти новые пути, выходящие из четвертой вершины с промежуточной вершиной 1. Строка 4 матрицы D1 переписывается из матрицы D0. Осталось рассчитать элементы Определим элементы матрицы D2. Вторую строку и второй столбец матрицы D2 переносим из матрицы D1.
Находим длины Матрицы D3, D4, D5 строятся аналогично. Приведем их без дальнейших пояснений (стр. 274). Построение деревьев кратчайших путей. В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев. Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D5) и ориентируясь по диаграмме на рис. 9. Деревья показаны на рис. 10.
Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы Dp по крайней мере одна длина сохраняется такой же, какой она была в матрице D0 (длина кратчайшего пути из одной дуги). В нашем случае имеем:
Эти числа показаны в матрице Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.
|