Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. E) открытием морских торговых путей
  2. EDI (Electronic Data Interchange) - международный стандарт обмена электронными данными; 2) передача стандартизированных электронных сообщений, заменяющих бумажные документы.
  3. I. Государство Израиль и международные отношения на Ближнем Востоке
  4. III Архангельского международного туристского форума
  5. III. Корейская война и укрепление «международного престижа» КНР
  6. III. Международные конфликты в Африке в 1980-1990-е гг.
  7. III. Новая роль Китая на международной арене

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути (и сам путь), соединяющий 2 произвольные фиксированные вершины s (начало) и t (конец).

Алгоритм Дейкстры:

1. В начале алгоритма все вершины не окрашены. Каждой вершине V во время выполнения алгоритма ставиться в соответствие либо L(V) – длина кратчайшего пути включающего только окрашенные вершины, L'(V) – временная метка, которая становиться равной L(V) в момент когда V окрашивается.

Полагаем что L(S)=0, L’(V)=∞, S≠V. Окрашиваем вершину S.

2. Для каждой неокрашенной вершины и соседней с последней из окрашенных вершинV пересчитываем L(U)=min{L’(U), L(V)+L(V,U)}, где L(V,U) – длина дуги между V и U.

Если L'(U)=∞ для любой неокрашенной вершины U, то алгоритм следует закончить. Так как в исходной сети не существует пути из S в неокрашенные вершины, в том числе и в Е. в противном случае находим вершины R, для которой L'(R) =L’(U), после чего К окрашиваем и вносим в корневое дерево дугу (V,R). Вершина R становится последней из окрашенных вершин.

3. В момент, когда вершина T становится окрашенной, находим кратчайший путь, соединяющий S и T, состоящий из окрашенных дуг.

3

 

4 7

 

 

3 2

 

L(S)=0 L(C)=3(S->C) L(A)=4 (S->A) L(D)=6(S->C->D) L’(b)=7(S->B) L(T)=8 (S->C->D->T)
L’(A)=4 L’(B)=7 L’(C)=3 L’(D)=3+3=6 L’(B)=7 L’(D)=6 L’(T)=8 L’(T)=9  

 


 


Дата добавления: 2015-10-13; просмотров: 73 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Способы задания графов| Сеть. Потоки на сетях. Задача нахождения потока максимальной мощности. Алгоритм Форда-Фалкерсона

mybiblioteka.su - 2015-2024 год. (0.007 сек.)