Найдите кратчайший путь из пункта один в пункт четыре. Рассматриваемая задача состоит в вычислении и указании пути, на котором достигается минимум конечного числа элементов. Транспортная сеть (с указанием расстояний) приведена на рисунке три.

Введём обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рисунке 1, в вершину 2 можно попасть либо сразу и...