Djikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the singlesource shortest paths problem.
The somewhat unexpected result that all the paths can be found as easily as one further demonstrates the value of reading the literature on algorithms!
This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree  it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph,
G = (V,E)  where 

S  the set of vertices whose shortest paths from the source have already been determined and  
VS  the remaining vertices. 
d  array of best estimates of shortest path to each vertex 
pi  an array of predecessors for each vertex 
The basic mode of operation is:
 Initialise d and pi,
 Set S to empty,
 While there are still vertices in VS,
 Sort the vertices in VS according to the current best estimate of their distance from the source,
 Add u, the closest vertex in VS, to S,
 Relax all the vertices still in VS connected to u
Relaxation
The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v. The relaxation procedure proceeds as follows:
initialise_single_source( Graph g, Node s ) for each vertex v in Vertices( g ) g.d[v] := infinity g.pi[v] := nil g.d[s] := 0;This sets up the graph so that each node has no predecessor (pi[v] = nil) and the estimates of the cost (distance) of each node from the source (d[v]) are infinite, except for the source node itself (d[s] = 0).
Note that we have also introduced a further way to store a graph (or part of a graph  as this structure can only store a spanning tree), the predecessor subgraph  the list of predecessors of each node, 
The relaxation procedure checks whether the current best estimate of the shortest distance to v (d[v]) can be improved by going through u (i.e. by making u the predecessor of v):
relax( Node u, Node v, double w[][] ) if d[v] > d[u] + w[u,v] then d[v] := d[u] + w[u,v] pi[v] := uThe algorithm itself is now:
shortest_paths( Graph g, Node s ) initialise_single_source( g, s ) S := { 0 } /* Make S empty */ Q := Vertices( g ) /* Put the vertices in a PQ */ while not Empty(Q) u := ExtractCheapest( Q ); AddNode( S, u ); /* Add u to S */ for each vertex v in Adjacent( u ) relax( u, v, w )
Operation of Dijkstra's algorithm
This sequence of diagrams illustrates the operation of Dijkstra's Algorithm.
This sequence of diagrams illustrates the operation of Dijkstra's Algorithm.
Initial graph All nodes have infinite cost except the source  
Choose the closest node to s. As we initialised d[s] to 0, it's s. Add it to S Relax all nodes adjacent to s. Update predecessor (red arrows) for all nodes updated.  
Choose the closest node, x Relax all nodes adjacent to x Update predecessors for u, v and y.  
Now y is the closest, add it to S. Relax v and adjust its predecessor.  
u is now closest, choose it and adjust its neighbour, v.  
Finally, add v. The predecessor list now defines the shortest path from each node to s. 
As usual, proof of a greedy algorithm is the trickiest part.
In this animation, a number of cases have been selected to show all aspects of the operation of Dijkstra's algorithm. Start by selecting the data set (or you can just work through the first one  which appears by default). Then select either step or run to execute the algorithm. Note that it starts by assigning a weight of infinity to all nodes, and then selecting a source and assigning a weight of zero to it. As nodes are added to the set for which shortest paths are known, their colour is changed to red. When a node is selected, the weights of its neighbours are relaxed .. nodes turn green and flash as they are being relaxed. Once all nodes are relaxed, their predecessors are updated, arcs are turned green when this happens. The cycle of selection, weight relaxation and predecessor update repeats itself until all the shortest path to all nodes has been found.
Key terms
 singlesource shortest paths problem
 A descriptive name for the problem of finding the shortest paths to all the nodes in a graph from a single designated source. This problem is commonly known by the algorithm used to solve it  Dijkstra's algorithm.
 predecessor list
 A structure for storing a path through a graph.