Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
МОТС / Часть1 / 13. Расскажите об алгоритме нахождения кратчайшего пути между двумя вершинами графа..doc
Скачиваний:
90
Добавлен:
22.03.2015
Размер:
568.32 Кб
Скачать
  1. Расскажите об алгоритме нахождения кратчайшего пути между двумя вершинами графа.

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

Дан неориентированный граф G=(X, U). Каждому ребру приписано некоторое число l(u) >= 0, называемое длиной ребра. При этом любая цепь будет характеризоваться длиной .

Требуется для двух произвольных вершин a и b графа G найти путь , причем такой, чтобы его длина была наименьшей.

Задача распадается на две:

  1. Нахождение кратчайшего пути в графе с ребрами единичной длины (или с ребрами равной длины).

  2. Нахождение кратчайшего пути в графе с ребрами произвольной длины.

А) Приписываем конечной вершине индекс 0.

Б) Помечаем 1 все смежные вершины.

В) Находим все вершины, смежные вершинам, имеющим индекс 1, и

приписываем им индекс 2.

Г) И т.д., пока не будут помечены все вершины. Значение индекса начальной вершины будет длиной пути.

Нахождение кратчайшего пути в графе с ребрами произвольной длины.

  1. Каждая вершина xi помечается индексом . Конечной вершине приписываем

индекс 0 =0. Для остальных вершин предварительно полагаем i = (i ).

  1. Ищем такую дугу (xi, xj), для которой i - j >l(uij), и заменяем индекс j индексом j’ = i + l(uij) < j. Продолжаем этот процесс замены индексов до тех пор, пока остается хотя бы одна дуга, для которой можно уменьшить j.

Если какую –то вершину можно пометить несколькими способами, то выбирается наименьшее значение.

Сформулируем правило для нахождения кратчайшего пути:

Пусть xn =a – начальная вершина с индексом n. Ищем вершину xp1, такую, что n - p1 = l(un,p1). Далее ищем вершину xp2, такую, что p1 - p2 = l(up1,p2) и т.д. до тех пор, пока не дойдем до конечной вершины.

Пример:

Найти кратчайший путь из вершины 6 в вершину 1.

  1. Вершине 1 присваиваем индекс «0». Для остальных вершин полагаем i = .

  2. Ищем дугу, для которой j - 1> l(xj,x1). Это дуги (x1, x2) и (x1, x3).

  3. Приписываем вершинам 2 и 3 индексы 2 = 1+ l(x0,x2) = 0 + 2 = 2; 3=1+l(x0,x3)=0+9=9.

  4. Далее ищем дуги, для которых j - 2 >l(xj, x2); j - 3 > l(xj, x3).

  5. Вершинам 4, 5 приписываем индекс 4 = 2 + l(x2, x4) = 2 + 3 = 5, 5=2+l(x2, x5)=2 + 3 = 5. Вершине 6 приписываем индекс 6=3+l(x3,x6)=9+7=16.

  6. Вершину 6 можно пометить из вершины 4, так как 6 - 4 > l(x4, x6);

16–5 > 6 ; 6 = 4 + l(x4, x6) = 5 + 6 = 11.

Находим кратчайший путь. Индекс вершины 6 равен 11, значит, длина кратчайшего пути равна 11. Ищем вершину, для которой 6 - j = l(x6, xj). Это вершина 4: 11-6=5. Значит, первой промежуточной вершиной на пути 6 – 1 является вершина 4. Далее ищем вершину, для которой 4 - j = l(x4, xj). Это вершина 2: 5 – 2 = 3. И так далее, пока не дойдем до вершины 1. Получаем кратчайший путь из вершины 6 в вершину 1: 6 – 4 – 2 – 1, длина которого равна индексу вершины 6, т.е. равна 11.