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

163 Поясним работу алгоритма Дейкстры, используя пример из [17]. Пусть имеем взвешенный орграф диаграмма которого представлена на рис. 5.34. Матрица весов М= (ту) этого графа имеет следующий вид: А в с D Е F А " 0 2 00 3 00 со В СО 0 00 4 со М =С 00 00 0 00 00 5 D 00 со 00 0 2 со Е со со 00 00 0 1 F оэ 00 о оэ 00 0 Допустим, что нужно найти кратчайший путь от вершины !Д к Рис. 5,34 любой - -Другой "«-"вер1пинё этого орграфа--. — В процессе работы алгоритма каждой вершине v орграфа присваивается число d[v], равное расстоянию от вершины ' ^ д о v. В начальный момент Величины fi?[v] совпадают с весом (длиной) дуги (A,v), если эта дуга существует, или равна со в противном случае. В течение работы алгоритма обходятся вершины орграфа и уточняются значения d{v]. На ка}кдом шаге алгоритма отмечается одна вершина и, до которой уже ххайден кратчайший путь OTV ) « расстояние d[u] до неё. Далее полученное значение d{u\ отмеченной вершины не меняется. Следовательно, на начально.м шаге используется та строка матрицы весов М, которая построена д л я вершины1^'Для оставшихся, не отмеченных вершин v, число <i[vl будет меняться с учётом того, что искомый кратчайший путь до них от | ^ у д е г проходить через последнюю отмеченную вершину и. Алгоритм завершается, когда все возможные вершины будут отмечены и получат свои окончательные значения d{v]. Работу алгоритма можно иллюстрировать с помош,ью следующей таблицы, каждая строка которой соответствует итерации (шагу) алгоритма. Шаг Отмеченные вершины Расстояние до вершины С D F Неотмеченные вершины В D 'С F ^ B. С, D, Е. F C. D, Е. F С, Е. F E,F