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

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

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

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

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

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

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

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

 

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

 

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