http://npc-news.ru/

Поиск кратчайшего пути

Задача поиска кратчайшего расстояния моделируется с помо­щью сетей или графов. К данной задаче сводятся многие задачи комбинаторной оптимизации. Существуют различные типы за­дач о кратчайшем пути: между двумя заданными вершинами, между заданной вершиной и всеми остальными вершинами сети, между каждой парой вершин и др.

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

Пусть задана связная сеть G из п + 1 вершин и гп ребер, представленная в виде ориентированного графа, в котором вы­делены две вершины — вход (нулевая вершина) и выход (вер­шина с номером п). Для каждой дуги заданы неотрицательные числа, называемые длинами дуг. Сеть представляется матрицей смежности А, в которой:

Для решения задачи, часто используют алгоритм Дейкстры, который признан одним из лучших. Рассмотрим принципы его построения.

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

Шаг 1. Определяются непосредственные расстояния (длиной в одно ребро) от заданной вершины Vq до всех остальных вершин.

Шаг 2. Выбирается наименьшее из них в качестве «постоян­ного» наименьшего расстояния (ребро между Vq и некото­рой новой вершиной Уд).

Шаг 3. Это наименьшее расстояние добавляется к длинам ре­бер от новой вершины Уд до всех остальных связанных с нею вершин.

Шаг 4. Эта сумма сравнивается с предыдущим расстоянием от Vq до остальных вершин, и прежнее расстояние заменя­ется, если новое меньше.

Шаг 5. Новая вершина удаляется из списка вершин, до кото­рых ещё не определены кратчайшие расстояния, и список укорачивается на один элемент.

Затем весь этот процесс повторяется, присоединяется новое кратчайшее расстояние к списку и т.д., пока конечная вершина не окажется соединенной с Vq путем из выделенных ребер.

В наихудшем случае задача отыскания кратчайшего расстоя­ния от начальной вершины до конечной имеет ту же сложность, что и задача отыскания кратчайшего пути из начальной верши­ны во все остальные вершины. Задача о кратчайшем пути имеет в наихудшем случае сложность 0((п+ I)2).


Комментарии закрыты.