Решение задачи о кратчайшем пути в транспортной сети непосредственно по графу

Пусть дан конечный граф, каждой дуге которого поставлено в соответствие число c_ij, называемое длиной дуги. Требуется найти путь наименьшей длины, ведущий из некоторой вершины S в некоторую вершину t. Рассмотрим один из алгоритмов решения данной задачи – алгоритм Минти. Он позволяет связать кратчайшими путями фиксированную вершину сети со всеми остальными.

Предварительный шаг. Пометим вершину S числом e_s = 0. Далее продолжаем расстановку пометок следующим образом. Помеченные вершины будем относить к множеству R, непомеченные – к множеству . Итак, S Î R.

Общий шаг. Итак, R – множество помеченных вершин. Хотя бы одна вершина всегда имеется в R. Каждой вершине i Î R поставлено в соответствие число e_i. Рассмотрим все дуги (), исходящие из множества помеченных вершин R и заканчивающиеся на непомеченных вершинах j Î . Найдем для каждой дуги () величину h_ij = e_i + c_ij. Выделим дуги, на которых достигается минимум этой суммы, и отметим числом e_j=min h_ij, (i Î R, jÎ ) те вершины j Î , на которых заканчиваются выделенные дуги. Будем производить таким образом помечивание вершин до тех пор, пока не пометим вершину t. Число e_t указывает длину кратчайшего пути от S к t.

Заключительный шаг. Искомый путь определяем, двигаясь от t к S по выделенным дугам в направлении, обратном их ориентации.

Таким образом, при решении задачи выполняется конечное число раз общий шаг и один раз заключительный шаг.