Кратчайшие пути для графов из одного источника (алгоритм Дейкстры)

алгоритм

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

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

Один из способов решения задачи поиска кратчайшего пути с одним источником:Dijkstraалгоритм.DijkstraАлгоритм сгенерирует дерево кратчайших путей, корнем дерева будет начальная вершинаs, ветви дерева исходят из вершинsвычислятьGКратчайший путь ко всем остальным вершинам в . Этот алгоритм требует, чтобы все значения в графе были неотрицательными. иPrimАлгоритм аналогичен,DijkstraАлгоритм также использует жадный алгоритм, который всегда добавляет кратчайшее ребро, которое в данный момент выглядит ближайшим к кратчайшему пути.

В корне,DijkstraАлгоритм выбирает вершину и непрерывно обнаруживает связанные с ней ребра, подобно поиску в ширину, чтобы найти текущую ближайшую точку.

Алгоритм потока:

1. 求从顶点`a`开始的单源最短路径，就是图中每个点距离`a`的最短路。

  1. искать из вершиныaНачальный кратчайший путь из одного источника — это расстояние между каждой точкой на графикеaкратчайший путь.

2. 选定`a`，标记访问过了，首先初始化图中各点与`a`的距离，在实际代码中一般用一个数组`dist[i]`存放这个值，如果暂时不可达，存一个极大值在里面。如图，只有`b`,`c` 直接与`a`连接，这时候`dist[b]=8`,`dist[c]=4`。其它点的`dist[i]=NaN,`后面的运算就是不断更新这个`dist`数组。

  1. выбранa, метка была посещена, сначала инициализируйте каждую точку на графике с помощьюaРасстояние в реальном коде обычно использует массивdist[i]Сохраните это значение. Если оно временно недоступно, сохраните в нем максимальное значение. Как показано, толькоb,cнепосредственно сaподключить, на этот разdist[b]=8,dist[c]=4. другая точкаdist[i]=NaN,Последующая операция заключается в постоянном обновлении этогоdistмножество.

3. 再选出`dist`最小的元素扩展，很明显是`c`，标记`visit`，这时候通过`c`点，`f`，`e`也产生一个新的与`a`的距离，这时候更新`dist`数组，他们之前与a的距离都是`NaN`，当然只要原来与`a`的距离大于通过`c`与`a`的距离，都需要更新。

  1. выбрать сноваdistМинимальное расширение элемента, очевидноc,отметкаvisit, на этот раз черезcточка,f,eтакже генерирует новый сaрасстояние, обновить на этот разdistмассивы, их предыдущие расстояния от a равныNaN, конечно если оригиналaрасстояние больше, чем черезcиaНеобходимо обновить расстояния.

4. 再找出非`visit`中`dist`最小的点，找到`f`，因为`b, d, e`都与`f`相邻，这时候比较通过`f`后与`a`的距离，如果比原来`dist`短，就更新`dist`。

  1. узнатьvisitсерединаdistнаименьшая точка, найденнаяf,так какb, d, eоба сfРядом, на этот раз сравнение проходитfпосле сaрасстояние, если оно больше исходногоdistкороче, обновлениеdist.

5. 选择顶点`b`。

  1. выберите вершинуb.

6. 在选择顶点`d, e`后形成最短路径。

  1. при выборе вершинd, eобразуют кратчайший путь.

DijkstraРеализация алгоритма:

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Source node will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]
Категории