Решение задачи о кратчайшем пути в графе

на основе линейного программирования [1,4]

Модель линейного программирования для задачи о кратчайшем пути строится следующим образом.Пусть X_ij,d_ij представляют соответственно величину и стоимость потока по дуге (i,j). Тогда задача о кратчайшем пути в сети с N узлами формулируется как:

минимизировать Z=

при ограничениях

=1 (исходный пункт),

= (для всех к # 1 или N)

=1 (пункт назначения)

Целевая функция требует, чтобы общее ”расстояние”, пройденное единицей потока, было минимальным. Здесь принято, что =1,если дуга (i,j) принадлежит кратчайшему пути и =0, если дуга (i,j) не принадлежит кратчайшему пути.

Кратчайший остов графа