Выбор алгоритма решения

Выбираем для решения задачи алгоритм Дейкстры, т. к данный алгоритм позволяет решить задачу комивояжера оптимальным способом.

Математическая модель

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм,. предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.

Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина. Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.

Какая же из неокрашенных вершин является (m + 1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m +1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине s. Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.