Дискретная математика

164 В каждой строке таблицы записываются отмеченная верышна, текущие значения d[v\ и оставшиеся неотмеченные вершины. При этом жирным шрифтом выделяется наименьшее из значений d{v] среди неотмеченных вершин. Используя выделенное (жирным шрифтом) значение 4^]= выбирается следующая отмеченная вершина. Кроме того, в построенной таблице все значения d[v\ для отмеченных вершин отделены от остальных ломаной линией. Рассмотрим орграф, представленный на рис. 5.34. Для этого графа требуется найти кратчайшие пути от вершины А. Шаги алгоритма будут следующие. Шаг 0. Отмечаем указанную вершину А и используем первую строку матрицы весов М для определения начальных значений rf[v]. Начальные значений <:^[v] будут совпадать со значениями, (i[v] записанными в первой строке матрицы весов М Шаг 1. Отмечаем вершину 5, так как для неё d[B] имеет наименьшее значение в предыдущей строке таблицы (и выделена жирным шрифтом). Вычисляем длины путей, ведущих пз А к неотмеченным вершинам через вершину В. Если новые значения d[v] оказываются меньше предыдущих, то меняем их на новые, иначе оставляем без изменения. Путь АБС имеет длину 3, а путь ABE - б, в то время как старые расстояния до этих вершин от Л были равны со. Следовательно, заменим d{C\ на 3 и d{E\ на 6. Шаг 2. Наименьшее значение d[v] (среди неотмеченных) имеют две вершины: С и D. Отмечаем любую из них, например, вершину D. Вычисляем длины путей, ведущих из ^ к неотмеченным вершинам через вершины В ^D. При этом значение d[E] будет равно 5, остальные останутся без изменения. Шаг 3. Наименьшее значение d[v] среди неотмеченных имеет вершина С. Отмечаем эту вершину С. Вычисляем длины путей, ведущих из А к неотмеченным вершинам через вершины В, D и С. При этом значение будет равно 8, остальные останутся без изменения. Шаг 4. Отмечаем верпшну Е, так как вершина Е имеет наименьшее значение d[v] (среди неотмеченных). Вычисляем длины путей, ведущих из Л к неотмеченным вершинам через вершины В, D, С я Е. При этом значение d[F] будет равно 6, остальные останутся без изменения. Шаг 5. Отмечаем вершину F. В результате отмечены все вершины и найдены все кратчайшие пути из вершины А до каждой достижимой из А вершины. Формальное представление алгоритма Дейкстры будет следующим. Отметим (еще раз), что этот алгоритм выбирает кратчайший путь от заданной вершииы (для рассмотренного примера от вершины А) до любой вершины орграфа v и присваивает его длину переменной (i[v], а в списке PUTH(v) перечисляются вершины кратчайшего пути от А до v.