Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Реферат: Решение задачи о кратчайшем пути в транспортной сети непосредственно по графу
РефератПомощь в написанииУзнать стоимостьмоей работы

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

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

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

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

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

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

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

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

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

Показать весь текст
Заполнить форму текущей работой

На отлично!