Задача о кратчайшем пути

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

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

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

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