Условие задачи
Решить задачу о кратчайшем маршруте аналитическим способом
Ответ
Для решения задачи разобьем все множество вершин на подмножества: в первое подмножество включаем исходную вершину 1, во второе вершины, в которые входят дуги из вершины 1, в третье вершины, в которые входят дуги из вершин второго подмножества и т.д. Получим пять подмножеств: {1}, {2,3,4}, {5,6,8}, {7,9}, {10}. Любой маршрут из вершины 1 в вершину 10 содержит ровно четыре дуги, тогда процесс решения задачи разбивается на четыре этапа. Нумеровать этапы будем от конечной вершины к начальной, обозначим n - номер шага, - минимальная длина пути из вершины s в вершину 10, если до нее осталось n ша...