Алгоритм поиска кратчайших расстояний на графе (Уоршалла).

74. (1 задача) Дан направленный граф, алгоритмом Уоршалла найти матрицу расстояний (замыкание графа) .

Алгоритм Уоршалла-Флойда работает Матричными преобразованиями (задача - обеспечение выполнения неравенства треугольника), критерий прекращения процесса неизменность расстояний после применения алгоритма на очередном шаге.

Решение примера:

Матрица после 1й итерации , матрица после 2-й итерации. Проверка показала, что 3я итерация совпадает со 2-й, поэтому алгоритм окончен.

75. (~ 1/1,5 задачи) Аналогично, алгоритмом Уоршалла решить задачу поиска кратчайших расстояний для ненаправленного графа (цепи).

Рисунок рисуется на весь лист – не менее А5.

Проверяется неравенство треугольника для каждого ребра. Если оно не выполняется, данному ре ребру приписывается новый вес как минимальный «двухзвенный» треугольный объезд по формуле . Изначальный граф может иметь любую форму. Для простоты дана форма 7-ми звенного цикла (~бензольного кольца). На первой итерации появятся стяжки инцидентных рёбер. На второй уже все исходно не существующие рёбра (рёбра ∞ длины) получат варианты конечного объезда – это однако не конец алгоритма.

Далее ещё две итерации потребуется, чтобы определить кратчайшие расстояния (Последними жертвами падут несколько старых стяжек). При уменьшении значения ребра пишется - старое берётся в скобки – рядом пишется новое. Рёбра также могут быть пересмотрены. На новых рёбрах, а также на старых, длины которых уменьшаются за счёт объезда, помимо расстояния ставится вершина, через которую производится объезд – по эти меткам как по грамматике можно восстановить.

Пример

Теперь по меткам восстановим цепочку наискорейшего проезда из С в А: СА→CDA→CBDA→CBDEA, её длину узнаём из последней метки на ребре СА.

Замечание по оформлению. Граф не обязательно перерисовывать. Можно обойтись одним достаточно крупным рисунком и пользоваться знаком → при переходе от одной метки к метке с более коротким объездом (см. пример).