2015-01-07
1290
Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так что дуге (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 = 
Длина пути (x 1, x 2, x 5, x 4) равна 1 + 5 + 6 = 12.
Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути.
Для нахождения минимального пути между двумя произвольными вершинами для случая, когда все cij ³0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана и др. [2,3,5].
|
|
|
Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице.
