2.2. Пример решения задачи методом Флойда

С помощью метода Флойда определим кратчайшие пути между вершинами нагруженного орграфа:

Решение.

1. Подготовительный шаг:

, .

2. Первый шаг ()..

Определяем элементы матрицы . При этом элементы первой строки и первого столбца матрицы, а также диагональные элементы остаются без изменений:

, ,.

Вычисляем остальные элементы матрицы :

,

,

,

,

,

.

Итак,

.

Определяем элементы матрицы .

Т.к. , то.

Т.к. , то.

Аналогично получаем

, ,,.

Итак,

.

3. Второй шаг ().

Определяем элементы матрицы . При этом элементы второй строки и второго столбца матрицы, а также диагональные элементы остаются без изменений:

, ,,,,

, .

Вычисляем остальные элементы матрицы :

,

,

,

,

,

.

Итак,

, .

Определяем элементы матрицы :

, ,,,

, ,,,

, ,,,

, ,,.

Введение в рассмотрение дополнительной вершины не меняет минимальные пути между вершинами.

4. Третий шаг ()..

Построив матрицы и, можно убедиться, чтои. Т.е. введение в рассмотрение дополнительной вершиныне меняет минимальные пути между вершинами.

5. Четвертый шаг ()..

Вводится в рассмотрение вершина и находятся минимальные пути, проходящие через эту вершину.

Определяем элементы матрицы :

, ,,,

, ,,

,

,

,

,

,

.

Итак,

.

Определяем элементы матрицы :

, ,,,

, ,,,

, ,,,

, ,,.

Итак,

.

По матрице определяем искомые минимальные пути (см. таблицу 2.1).

Таблица 2.1. Минимальные пути