Dijkstra finds the shortest path from a source to all destination in a directed graph (single source shortest path problem). During this process it will also determine a spanning tree for the graph.

A graph is made of out nodes and directed edges which defines a connection from one node to another node. A node (or vertex) is a discrete position in a graph. Edges can be directed an undirected. Edges have an associated distance (also called costs or weight). The distance between two nodes a and b is labeled as [a,b].

The mathematical description for graphs is G= {V,E}, meaning that a graph is defined by a set of vertexes (V) and a collection of edges.

The "order" of a graph is the number of nodes.

The "size" of a graph is the number of edges.

Typical graph problems are:

The following will focus on finding the shortest path from one node to another node in a graph.

The idea of Dijkstra is simple.

Dijkstra partitions all nodes into two distinct sets. Unsettled and settled. Initially all nodes are in the unsettled sets, e.g. they must be still evaluated. A node is moved to the settled set if a shortest path from the source to this node has been found.

Initially the distance of each node to the source is set to a very high value.

First only the source is in the set of unsettledNodes.

The algorithms runs until the unsettledNodes are empty. In earch iteration it selects the node with the lowest distance from the source out the unsettled nodes. If reads all edges which are outgoing from the source and evaluates for each destination node in these edges which is not yet settled if the known distance from the source to this node can be reduced if the selected edge is used. If this can be done then the distance is updated and the node is added to the nodes which need evaluation.

In Pseudocode the algorihm can be described as follows. Please note that Dijkstra also determines the presuccessor of each node on its way to the source. I'll leave that out of the pseudo code to simplify it.

				

Foreach node set distance[node] = HIGH
SettledNodes = empty
UnSettledNodes = empty

Add sourceNode to UnSettledNodes
distance[sourceNode]= 0

while (UnSettledNodes is not empty) {
	evaluationNode = getNodeWithLowestDistance(UnSettledNodes)
	remove evaluationNode from UnSettledNodes 
    add evaluationNode to SettledNodes
    evaluatedNeighbors(evaluationNode)
}

getNodeWithLowestDistance(UnSettledNodes){
	find the node with the lowest distance in UnSettledNodes and return it 
}

evaluatedNeighbors(evaluationNode){
	Foreach destinationNode which can be reached via an edge from evaluationNode AND which is not in SettledNodes {
		edgeDistance = getDistance(edge(evaluationNode, destinationNode))
		newDistance = distance[evaluationNode] + edgeDistance
		if (distance[destinationNode]  > newDistance ) {
			distance[destinationNode]  = newDistance 
			add destinationNode to UnSettledNodes
		}
	}
}