Dijkstra's Algorithm - Shortest Path Algorithm

"Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, producing a shortest path tree.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined." - Wikipedia

INITIALISE_SINGLE_SOURCE(G, start)
{
  for each vertex v ∈ v(G)
    dist[v] <- ∞
    pred[v] <- NIL
  dist[start] <- 0
}
// dist[v] <- distance of vertex "v" from vertex "start"
// pred[v] <- predecessor of "v" in the shortest path 
//            from "start"

RELAX(u, v, cost)
{
  if dist[v] > dist[u] + cost[u, v]
    dist[v] <- dist[u] + cost[u, v]
    pred[v] <- u
} 

DIJKSTRA(G, cost, start)
{
  INITIALISE_SINGLE_SOURCE(G, start)
  S <- φ
  Q <- V[G]
  while Q ≠ φ do
    u <- EXTRACT_MIN(Q)
    S <- S U {u}
    for each vertex v ∈ Adj[u]
      do RELAX(u, v, cost)
}
// S <- Set of vertices whose final shortest path weights
//      from the source (start) have already been determined
// Q <- min_priority queue of vertices, keyed by their 'dist'
//      values

Written by Munia Balayil