Задача поиска кратчайших расстояний между всеми парами вершин графа

Пусть имеется граф G со множеством вершин V={v₁,…,v_n}. Обозначим через длину кратчайшего пути из v_i в v_j с промежуточными вершинами во множестве {v₁,…,v_m}. Рассмотрим алгоритм Флойда-Уоршалла нахождения матрицы D, элементы которой – кратчайшие пути между всевозможными парами вершин графа G. Алгоритм использует три правила:

1. , где a_ij – вес дуги, соединяющий вершины v_i и v_j.

2. .

3. Длина кратчайшего пути из вершины v_i в вершину v_j

.

Если , то алгоритм Флойда-Уоршалла содержит n шагов. Если из вершины v_i нет дуги в вершину v_j, то считаем вес дуги равным ¥. Для ребер, являющихся петлями, считаем вес дуги равными 0, т.е. в матрице D⁰ зануляем диагональ.

Пример 4.14. Найдем матрицу кратчайших расстояний для графа.

Элементы матрицы D⁽¹⁾ находим по правилу . Получаем .

Элементы матрицы D⁽²⁾ находим по правилу .

Элементы матрицы D⁽³⁾ находим по правилу .

.