Лекция: Задача о кратчайшем пути

Пусть имеется сеть с источником s и стоком t. Известно расстояние между i-м и j-м узлами – cij. Необходимо найти кратчайший путь от начального узла до конечному узла.

Обозначим через xij булеву переменную, которая равна 1, если узел принадлежит кратчайшему пути, и 0 – в противном случае.

Экономико-математическая модель задачи:

Первое ограничение означает, что единица потока втекает их источника s; второе ограничение – что единица потока втекает в сток t; третье ограничение гарантирует сохранение потока при протекании по сети.