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

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

Постановка задачи состоит в следующем. Задан конечный ориентированный граф 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 и т.д.

Рис..1.

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

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