Dijkstra’s Shortest Path Algorithm

Summary. The article formalizes Dijkstra’s shortest path algorithm [11]. A path from a source vertex v to a target vertex u is said to be the shortest path if its total cost is minimum among all v-to-u paths. Dijkstra’s algorithm is based on the following assumptions: • All edge costs are non-negative. • The number of vertices is finite. • The source is a single vertex, but the target may be all other vertices. The underlying principle of the algorithm may be described as follows: the algorithm starts with the source; it visits the vertices in order of increasing cost, and maintains a set V of visited vertices (denoted by UsedVx in the article) whose cost from the source has been computed, and a tentative cost D(u) to each unvisited vertex u. In the article, the set of all unvisited vertices is denoted by UnusedVx. D(u) is the cost of the shortest path from the source to u in the subgraph induced by V ∪ {u}. We denote the set of all unvisited vertices whose Dvalues are not infinite (i.e. in the subgraph each of which has a path from the source to itself) by OuterVx. Dijkstra’s algorithm repeatedly searches OuterVx for the vertex with minimum tentative cost (this procedure is called findmin in the article), adds it to the set V and modifie