Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры.

Если задан орграф G(V, E), в котором дуги помечены числами и эти числа обычно называют весами или длинами, то орграф можно представить в виде матрицы весов.

||Cij|| =

Длиной пути называется сумма длин дуг, входящих в этот путь. Наиболее часто на практике встречается задача отыскания кратчайшего пути. Алгоритм Флойда находит все кратчайшие пути между всеми парами вершин в орграфе. Алгоритм ДХ3 находит кратчайший путь между двумя данными вершинами орграфа, если длины дуг неотрицательны.