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

И вот, представив схему метро в виде связного смешанного взвешенного графа, мы наконец можем выбрать маршрут поездки.

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

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

Кроме того, сами пути можно искать, следуя разным принципам: двигаясь по ребрам с наименьшим весом (предполагая, что чем меньше каждое из слагаемых, тем меньше будет итоговая сумма), перебирая как можно больше вариантов ответвлений (поиск «в ширину») или последовательно идущих ребер (поиск «в глубину»).

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

#математика
#Соловьева