Раздел «Алгоритмы».DijkstraAlgo:

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

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

Пусть дан ориентированный взвешенный граф G=(V,E) с весовой функцией w:E\to\mathbb{R} , где V — множество вершин в графе, E — множество рёбер. Весом пути p=(v^0, v^1, ..., v^k) называется сумма весов всех рёбер, входящих в этот путь. Вес кратчайшего пути из u в v: \delta(u,v)=\min(w(p)) для всех путей р из u в v, если путь существует, иначе бесконечность. Задача состоит в том, чтобы для данного взвешенного графа G и начальной вершины s найти кратчайшие пути из s во все вершины v\in V .

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G=(V,E) c исходной вершиной s, в котором веса всех рёбер неотрицательны, для всех (u,v)\in E.

Идея решения

Сначала рассмотрим две вспомогательные процедуры. Для каждого ребра v\in V мы храним некоторе число d[v], являющееся верхней оценкой веса кратчайшего пути из s в v. Для каждой вершины v\in V мы будем помнить её предшественника \pi[v]. Начальные значения оценки кратчайшего пути и массива \pi устанавливаются процедурой:

Initialize(G,s):

1:foreach %$v\in V[G]$%
2:      do {
3:        %$ d[v]\leftarrow \infty $%
4:        %$ \pi[v]\leftarrow NIL $%
5:      }
6:%$ d[s]\leftarrow 0 $% 

Также нам будет необходима техника релаксации рёбер.Релаксация ребра (u,v)\in E состоит в следующем: значение d[v] уменьшается до d[v]+w(u,v) (если второе значение меньше первого); при этом d[v], очевидно, остаётся верхней оченкой. При этом необходимо менять также и \pi[v], если мы хотим (а мы хотим:)), чтобы значение \pi[v] указывало путь, использованый для получения этой оценки.

Relax(u,v,w):

1:foreach %$v\in V[G]$%
2:      do {
3:        %$ d[v]\leftarrow \infty $%
4:        %$ \pi[v]\leftarrow NIL $%
5:      }
6:%$ d[s]\leftarrow 0 $% 
1:      if %$d[v]>d[u]+w(u,v)$% 
2:          then {
3:                %$d[v]\leftarrow d[u]+w(u,v)$%
4:                %$\pi[v]\leftarrow u$%
5:              }
В процессе работы алгоритма Дейкстры поддерживается множество S\subseteq V, состоящее из вершин v, для которых \delta(s,v) уже найдено (то есть d[v]=\delta(s,v) ). Алгоритм выбирает вершину u\in V\setminus S с наименьшим d[u], добавляет u к множеству S и проводит релаксацию всех рёбер, выходящих из u, после чего цикл повторяется. Вершины, не лежащие в S, хранятся в очереди Q с приоритетами, определяемыми значениями функции d. Предполагается, что граф задан с помощью списков смежных вершин. Принципиальная схема алгоритма:

Dijkstra(G,s,w):

1:foreach %$v\in V[G]$%
2:      do {
3:        %$ d[v]\leftarrow \infty $%
4:        %$ \pi[v]\leftarrow NIL $%
5:      }
6:%$ d[s]\leftarrow 0 $% 
1:      if %$d[v]>d[u]+w(u,v)$% 
2:          then {
3:                %$d[v]\leftarrow d[u]+w(u,v)$%
4:                %$\pi[v]\leftarrow u$%
5:              }
1:%$Initialize(G,s)$%
2:%$S\leftarrow\varnothing$%
3:%$Q\leftarrow V[G]$%
4:  while %$Q\neq \varnothing$%
5:      do {  
6:        %$u\leftarrow Extractmin(Q)$% 
7:        %$S\leftarrow S\cup{u}$%  
8:        foreach  %$v\in Adj[u]$%  
9:        do %$Relax(u,v,w)$%
10:      } 

Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать. что он относится к жадным алгоритмам.

Примеры реализаций