Описание тега dijkstra

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

Псевдокод:

function Dijkstra(Graph, source):
   for each vertex v in Graph:            // Initializations
       dist[v] := infinity ;              // Unknown distance function from source to v
       previous[v] := undefined ;         // Previous node in optimal path from source
   end for ;
   dist[source] := 0 ;                    // Distance from source to source
   Q := the set of all nodes in Graph ;   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                  // The main loop
       u := vertex in Q with smallest distance in dist[] ;
      if dist[u] = infinity:
          break ;                        // all remaining vertices are inaccessible from source
      end if ;
      remove u from Q ;
      for each neighbor v of u:          // where v has not yet been removed from Q.
          alt := dist[u] + dist_between(u, v) ;
          if alt < dist[v]:              // Relax (u,v,a)
              dist[v] := alt ;
              previous[v] := u ;
              decrease-key v in Q;       // Reorder v in the Queue
          end if ;
      end for ;
  end while ;
  return dist[] ;
end Dijkstra.

Ссылка:

• Статья в Википедии