на основе линейного программирования [1,4]
Модель линейного программирования для задачи о кратчайшем пути строится следующим образом.Пусть Xij,dij представляют соответственно величину и стоимость потока по дуге (i,j). Тогда задача о кратчайшем пути в сети с N узлами формулируется как:
минимизировать Z=
при ограничениях
=1 (исходный пункт),
= (для всех к # 1 или N)
=1 (пункт назначения)
Целевая функция требует, чтобы общее ”расстояние”, пройденное единицей потока, было минимальным. Здесь принято, что =1,если дуга (i,j) принадлежит кратчайшему пути и =0, если дуга (i,j) не принадлежит кратчайшему пути.
Кратчайший остов графа