Экстремальные задачи на графах

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

Постановка задачи

Постановка задачи состоит в следующем. Задан конечный ориентированный граф G(x,гx), или G(x,u). Каждой дуге графа «u» поставлено в соответствие некоторое число l(u)³0, называемое длинной дуги «u». Длинной пути m называется сумма длин дуг, составляющих данный путь.

.

Требуется для двух фиксированных вершин x_o и x_n графа G(x,u) найти самый короткий соединяющий их путь.

К данной задаче может быть сведена следующая задача экономического содержания. Задана сеть дорог, соединяющих пункты x_i (i=0,1,…,n). Найти путь, соединяющий пункты x_o и x_n, по которому можно доставить груз в кратчайшее время. При этом время доставки груза из пункта x_i в x_j (i,jÎ0,…,n) задано и равно l(u_ij)=l(x_i,x_j)³0.

Если под длинной дуги l(x_i,x_j) понимать стоимость перевозки груза из пункта x_i в x_j, то содержание задачи составит определение такого пути из пункта x_i в x_j, на котором затраты на транспортировку были бы минимальными.

Пример.

Имеем 6 пунктов Х (x₀,…,x₆). Сеть дорог, связывающих эти пункты, изображена на графе (рис.3.3.1).

Время доставки груза из i-го пункта в j-й, т.е. l(x_i,x_j), задано и изображено числом в кружке, записанным рядом с дугой (x_i,x_j). Так, l(x₀,x₁)=2, l(x₀,x₂)=4, l(x₀,x₃)=5, l(x₁,x₄)=3 и т.д.

Рис. 3.3.1

Требуется определить путь, по которому из пункта x₀ в пункт x₅ можно доставить груз в кратчайшие время, и само кратчайшее время доставки.

Итак, задача о кратчайшем пути между двумя фиксированными вершинами ориентированного графа предполагает, во-первых, определение длины кратчайшего пути, во-вторых, определение самого кратчайшего пути.