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

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

 

Рассмотрим решение задачи на примере исходного графа, изображённого на рис. 3.7. Необходимо для него сформировать минимальное остовное дерево.

 

Рис. 3.7 Исходный граф

Решать данную задачу, как задачу линейного целочисленного программирования. Для этого необходимо сформировать целевую функцию и ограничения, накладываемые на переменные.