Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 110
Текст из файла (страница 110)
Продемонстрируем алгоритм Дейкстры с использованием матриц и покажем соответствующий граф. Упорядоченные пары, связанные с вершинами, введем аналогично предыдущему примеру, после чего получим рис. 14.92. б ~% б г Рис. !491 Вместо того, чтобы использовать предыдущую вершину о, в качестве второй координаты для вершины, принадлежащей пути, для представления вершины о, 616 ГЛАОА 14. Некоторые специальные вопросы гпеории графов используем только индекс г. Таким образом, вместо записи иу(т,тч), где т— присвоенное расстояние от вершины иг к еуч а и; — предыдушая вершина пути, используем запись иу(т, г).
Первоначально установим Ргео(4) = 0 для 1 < 1 < 5, т.к. в данный момент ни одна из вершин не имеет предшественника. Положим Р(1) = О, Т(1) = оо и И'г — — сю для 1 < ) < 5. Это делает вершину иг постоянной вершиной и приводит к ситуации, изображенной на рис. 14.93. к (ьь,О) 8 кАко,О) 2пъ24 ,(О,О) 4 к4ьь,О) Рис. 14.93 Прибавляем Р(1) = 0 к каждому элементу матрицы-строки И'(1) = (И кы И ш, И гз, И ы, Игге) = (со, 2, оо, 6, оо) Точнее, полагаем Бит = Р(1)+Иг(1). Для Бит()') < Т(г'), полагаем ргес1Я = 1.
Затем полагаем Т = Т д Бит, так что Т = (оо,2„оо,6, со). Это не что иное, как присваивание расстояния вершинам, смежным с вершиной иы Для наименьшего г такого, что Т(г) = шш(Т(у): 1 < ) < 5), полагаем Р(1) = Т(4), Т(1) = со и И'; = оо при 1 < ) < 5. Этим определяется выбор вершины иг как второй постоянной вершины.
Полагаем И = 2. (Переменная И отслеживает последнюю постоянную вершину.) Таким образом, Т = (оо,со,оо,б,оо), Р = (0,2,со,оо,оо) и ргег1 = (0,1,0,1,0). Матрица И' имеет вид со оо оо 6 оо оо со 4 со 8 оо оо 0 6 2 оо оо 6 0 4 оо оо 2 4 0 Получаем граф, изображенный на рис. 14.94. "(2~1) 8 "я" О) 2 кЪ 4 ,(О,О) ' .(5,1) Теперь прибавляем Р(2) = 2 к каждому элементу матрицы-строки И' (2) = (И'г ы И'гг, И'гз, И'г4, Иггз) = (со, со, 4, оо, 8) Точнее, пусть Бит = Р(2) + Иг(2), что дает расстояние от вершины иг к каждой вершине, смежной с вершиной иг, вдоль пути, проходяшего через иг. Для РАЗДЕЛ 74.6 Вгаешенные графы и алгоритмы поиска кратчайшего пути 617 ЯитЦ) < Т(1) полагаем ргес)Я = 2.
Далее, пусть Т = Т А Бит, так что Т = (оо, оо, 6, 6, 10), и для наименьшего 1 такого, что Т(1) = ш1п(Т(1): 1 < 1 < 5), полагаем Р(1) = Т(4), Т(1) = со и Иггч = оо при 1 < ) < 5. Таким образом, из выбрана как постоянная вершина. Полагаем И = 3. В результате Т = (сю, оо, со,6,10), Р = (0,2,6,оо,со) и ргес1 = (0,1,2,1,2). Матрица Иг имеет вид оо оо оо 6 со оо оо оо со 8 со оо оо 6 2 оо оо оо 0 4 оо оо оо 4 0 Получаем граф, изображенный на рис. 14.95.
1'г(~,1) З ~1(Ы,Р) г г (О,О) о (5,1) Рис. 14,95 Теперь прибавляем Р(3) = 6 к каждому элементу матрицы-строки И~(3) = (Из1, Исзз, Изз, Игзг, Исзз) = (оо, оо, оо, 6, 2). Точнее, полагаем Бит = Р(3) + И'(3), что дает расстояние от вершины и1 к каждой вершине, смежной с вершиной из, вдоль пути, проходящего через вершину из. Для Бит()') < Т()') полагаем Ргес)()') = 3. Далее полагаем Т = Т л Бит, так что Т = (оо, сю, сю, 6,8), и для наименьшего 1 такого, что Т(1) = ш1п(Т(~): 1 < 9 < 5), полагаем Р(1) = Т(1), Т(1) = оо и Исгч = со при 1 < у' < 5. Это определяет выбор вершины и4 как постоянной вершины. В результате Т = (оо, оо, оо,оо, 10), Р = (0,2,6,6,со), рта = (0,1,2,1,3), а со 8 со 2 оо 4 оо 0 Имеем граф, изображенный на рис.
14.96. Рис. 44.96 Наконец, прибавляем Р(4) = 6 к каждому элементу матрицы-строки И (4) = (И 41, И 42, И 43, И'44, И 4з) = (оо, оо, оо, оо,4). 618 ГЛКВА 14. Некоторые специальные вопросы теории графов Точнее, полагаем Бит = Р(4)+ И'(4). Это дает расстояние от вершины и~ к каждой вершине, смежной с вершиной и4, вдоль пути, проходящего через вершину иг. Для Битп()') < Т()') полагаем ргеН(~) = 4.
Далее полагаем Т = Т д Бит, так что Т = (оо, оо, оо, со,8), и для наименьшего г такого, что ТЯ = ш)п(Т(~): 1 < г < 5), полагаем Р(1) = Т(1), Т(1) = оо и Иг~; = оо для 1 < 1 < 5. Это определяет выбор вершины из как последней постоянной вершины.
В результате имеем Т = (со, оо, оо, оо, со), Р = (О, 2, 6, 6, 8), ргей = (О, 1, 2, 1, 3), а Таким обраазом, мы получили граф, изображенный иа рис. 14.97, и завершили алгоритм. Длина пути равна 8. Отслеживая путь, как в первом примере, находим, что игигизиз — кратчайший путь. Теперь рассмотрим алгоритм Флойда-Уоршолла. Этот алгоритм обладает преимуществом большей эффективности по времени и объему требуемой памяти. Используя алгоритм, также можно найти кратчайшее расстояние между двумя вершинами. Данный алгоритм очень напоминает алгоритм Уоршолла, который использовался для нахождения всех путей в графе путем определения матрицы А, где Асу = 1 тогда и только тогда, когда существует путь из вершины и, в вершину и .
В предыдущем случае мы отыскивали все пути длины 1. Далее— множество всех 2-путей, в которых серединной вершиной была вершина и,, и множество комбинировались затем со всеми путями длины 1. Затем отыскивали все пути длины 3 или менее, проходящие через вершину и, и/или иг и/или из (если такие существовали), и продолжали процесс до тех пор, пока ие находили все пути длины и или менее, проходящие через любую из и вершин. На этот раз, вместо нахождения путей из вершины и, к вершине и,, иа каждом этапе находим длину пути и сравниваем ее с найденной ранее длиной кратчайшего пути из вершины и, в и (если ои существует) и заменяем предыдущее значение в 1-ой строке и уком столбце новой длиной, если найден более короткий пути из и; к и .
Очевидно, что иа этот момент имеется две длины. Одна длина определена суммированием длин всех ребер, входящих в путь. Другая— нормальная длина пути, равная числу ребер пути. Надеемся, что удастся избежать путаницы, если говоря о длине ребра, иметь в виду его вес, как это было при рассмотрении алгоритмов Дейкстры. РАздеп 14.5. Взвешенные графы и алгоритмы поиска кратчаишего пути 619 1-й алгоритм Флойда-Уоршолла (1) Посмотрим на столбец 1 матрицы А. Если в г-ой строке столбца имеется положительное целое число, добавить его к строке 1, чтобы сформировать А'. Положить А равной 1-ой строке матрицы А и заменить ~-ую строку матрицы А на А,' д Агр Назвать эту матрицу АП1. (2) Рассмотреть столбец 2 матрицы А1'>, построенной на шаге 1.
Если в ~-ой строке столбца имеется положительное целое число, добавить его к строке 2, чтобы сформировать Аз. Положить А, равной ~'-ой строке матрицы А и заменить 1-ую строку матрицы АОО на А~~АА . Назвать эту матрицу А<з1. (3) Рассмотреть столбец 3 матрицы А1з1, построенной на шаге 2. Если в 1-ой строке столбца имеется положительное целое число, добавить его к строке 3, чтобы сформировать Аз. Положить Ау равной г-ой строке матрицы А и заменить 1-ую строку матрицы АОО на АздА,. Назвать эту матрицу А<з1. (4) Продолжать процесс, рассматривая следующий, например, 1-ый столбец матрицы, построенной на предыдущем шаге.
Если в гчой строке этого столбца имеется положительное целое число, добавить его к соответствующей строке, чтобы сформировать А*. Положить А равной 1-ой строке матрицы А и заменить 1-ю строку матрицы АО Ы на А' лА . Назвать эту матрицу АО1. (5) Продолжать, пока все столбцы не будут проверены. ПРИМЕР 14.88. Задан граф, изображенный на рис. 14.98. гг 1 г 3 о г 3 Рис. И.9о Пусть А — матрица, где А„— вес ребра (о,, о;), если ребро существует и со в противном случае. В рассматриваемом случае О 2 оо 3 оо 2 О 4 оо 1 оо 4 О 6 2 3 сю 6 О 3 оо 1 2 3 О А= Найдем вес всех путей длины 2, или 2-путей, в которых средней вершиной является вершина ог.
Начинаем с первого столбца. Находим первую строку в столбце 1, в которой имеется положительное целое число. В данном случае это Ниже приведены два алгоритма вычисления А. Первый алгоритм более удобен при вычислениях вручную. Второй — для реализации на компьютере. Он приводится в конце раздела. 620 ГЛАВА т4. Некоторые специальные вопросы теории графов число 2 в строке 2. Таким образом, существует ребро из вершины оз к вершине иг весом 2. Если в строке 1 на позиции (1, 1) имеется целое число тп, то существует ребро из вершины и1 к вершине о весом гп. Тогда 2+ т — вес 2-пути из вершины оз в вершину и .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
