Кратчайший маршрут во взвешенном связном графе

Если имеем орграф, то можно удалить вершины источники и стоки, не являющиеся началом и концом искомого маршрута, и так как кратчайший путь не проходит дважды ни через дугу, ни через вершину, то дуги, входящие в вершину начала пути и выходящие из конца пути, можно также исключить (см. рис. 2.25). После их исключения могут образоваться вершины источники, изолированные и тупиковые вершины, и даже компоненты связности, не содержащие вершин начала и конца маршрута. Их также следует исключить.

В неорграфе можно исключить висячие вершины.

Рисунок 2.25