ВУЗ:
Составители:
Рубрика:
51
тервале, связанных с покупкой автомобиля, вершинами некоторо-
го графа. Для упрощения в качестве моментов времени сделок
можно рассматривать лишь первые дни каждого месяца, квартала
или другого временного отрезка. Изобразим в данном графе факт
приобретения автомобиля дугой, соединяющей вершину, соответ-
ствующую моменту покупки, с вершиной, соответствующей мо-
менту окончания срока службы автомобиля. Весом дуги построен-
ного графа является стоимость соответствующей сделки.
Чтобы выбрать вариант с минимальной суммарной стоимостью,
необходимо среди всех возможных путей из вершины, соответст-
вующей начальному моменту времени, в вершину, соответствую-
щую конечному моменту времени, найти путь наименьшей длины.
Определение.
Путь наименьшей длины между вершинами s и t
будем называть расстоянием от s до t и обозначать через D(s,t).
Первый эффективный алгоритм решения задачи нахождения
кратчайшего пути в графе между двумя фиксированными верши-
нами при условии, что все дуги графа имеют неотрицательный вес,
предложил в 1959г. Е.Дейкстра.
Идея алгоритма.
Нахождение расстояния от s до t начинается с
вершины s и ведется методом поиска в ширину.
На каждой итерации алгоритма всякая вершина v графа G имеет
метку l(v) , которая может быть постоянной или временной. Если
метка l(v) является постоянной, то она равна расстоянию D(s,v)
(т.е. кратчайшему пути от s до v). Если же метка l(v) временная, то
l(v) - длина кратчайшего пути от s до v, проходящего через верши-
ны с постоянными метками. Таким образом, временная метка l(v)
является оценкой сверху для расстояния D(s,v) , и, став на некото-
рой итерации постоянной, она остается такой до конца работы ал-
горитма.
Кроме l(v) с каждой вершиной v графа G, за исключением s,
связывается еще одна метка -
θ
(v). На каждой итерации
θ
(v) явля-
ется номером вершины, предшествующей v, в пути от s до v, про-
ходящем через вершины с постоянными метками и являющимися
кратчайшим среди всех таких путей.
После того, как вершина t получит постоянную метку, с помо-
щью меток
θ
(v) легко указать последовательность вершин, состав-
ляющих кратчайший путь от s до t.
Перед началом первой итерации алгоритма вершина s имеет
постоянную метку l(s)=0, а метки l всех остальных вершин равны
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
