REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/21572
Tytuł: Dijkstra’s Shortest Path Algorithm
Autorzy: Chen, Jing-Chao
Data wydania: 2003
Data dodania: 19-lis-2026
Wydawca: University of Białystok
Źródło: Formalized Mathematics, Volume 11, Issue 3, Pages 237-247
Abstrakt: 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 D-values 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 modifies D-values by a procedure, called Relax. Suppose the unvisited vertex with minimum tentative cost is x, the procedure Relax replaces D(u) with min{D(u),D(u)+cost(x, u)} where u is a vertex in UnusedVx, and cost(x, u) is the cost of edge (x, u). In the Mizar library, there are several computer models, e.g. SCMFSA and SCMPDS etc. However, it is extremely difficult to use these models to formalize the algorithm. Instead, we adopt functions in the Mizar library, which seem to be pseudo-codes, and are similar to those in the functional programming language, e.g. Lisp. To date, there is no rigorous justification with respect to the correctness of Dijkstra’s algorithm. The article presents first the rigorous justification.
Afiliacja: Donghua University Shanghai
URI: http://hdl.handle.net/11320/21572
ISSN: 1426-2630
e-ISSN: 1898-9934
Typ Dokumentu: Article
metadata.dc.rights.uri: https://creativecommons.org/licenses/by-sa/4.0/
Właściciel praw: © 2003 University of Białystok
This work is licensed under the Creative Commons License.
Występuje w kolekcji(ach):Formalized Mathematics, 2003, Volume 11, Issue 3

Pliki w tej pozycji:
Plik Opis RozmiarFormat 
Dijkstra’s_Shortest_Path_Algorithm.pdf103,04 kBAdobe PDFOtwórz
Pokaż pełny widok rekordu Zobacz statystyki


Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL Creative Commons