Экстремальные пути в нагруженных ориентированных графах
Ориентированный граф называется нагруженным,если дугам этого графа поставлены в соответствие веса, так что дуге (xi,xj)сопоставлено некоторое число c(xi,xj)= cij, называемое длиной(или весом,или стоимостьюдуги). Длиной(или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (xi,xj), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е.
l(s)= 
cij,
причем суммирование ведется по всем дугам(xi, xj) 
s.
Матрица C = (cij) называется матрицей длин дуг или матрицей весов.
Рис. 3.10
Для графа, изображенного на рис. 3.10, матрица C имеет вид:
C = 
Длина пути (x1, x2, x5, x4) равна 1 + 5 + 6 = 12.
Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути.
Для нахождения минимального пути между двумя произвольными вершинами для случая, когда все cij ³0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана и др. [2,3,5].
Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице.
3.8 Алгоритм Форда – Беллмана нахождения минимального пути