Краткое напоминание: целочисленные полиэдры и комбинаторные задачи, тотальная унимодулярность и тотальная двойственная целочисленность. Доказательство тотальной двойственной целочисленности политипа паросочетаний в графе общего вида. Условия дополняющей нежесткости в паре линейно двойственных программ. Задача о кратчайших путях в направленном графе, запись в виде линейной программы, потенциалы вершин и приведенные длины. Прямо-двойственный алгоритм поиска кратчайшего пути.

https://books.google.ru/books?id=u1RmDoJqkF4C&lpg=PA109&ots=S8wLM_9-H9&pg=PA109&hl=ru (Section 5.4)