REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/21543
Tytuł: The Underlying Principle of Dijkstra’s Shortest Path Algorithm
Autorzy: Chen, Jing-Chao
Nakamura, Yatsuka
Data wydania: 2003
Data dodania: 17-lis-2026
Wydawca: University of Białystok
Źródło: Formalized Mathematics, Volume 11, Issue 2, Pages 143-152
Abstrakt: A path from a source vertex v to a target vertex u is said to be a shortest path if its total cost is minimum among all v-to-u paths. Dijkstra’s algorithm is a classic shortest path algorithm, which is described in many textbooks. To justify its correctness (whose rigorous proof will be given in the next article), it is necessary to clarify its underlying principle. For this purpose, the article justifies the following basic facts, which are the core of Dijkstra’s algorithm. • A graph is given, its vertex set is denoted by V. Assume U is the subset of V, and if a path p from s to t is the shortest among the set of paths, each of which passes through only the vertices in U, except the source and sink, and its source and sink is s and in V, respectively, then p is a shortest path from s to t in the graph, and for any subgraph which contains at least U, it is also the shortest. • Let p(s, x,U) denote the shortest path from s to x in a subgraph whose the vertex set is the union of {s, x} and U, and cost (p) denote the cost of path p(s, x,U), cost(x, y) the cost of the edge from x to y. Give p(s, x,U), q(s, y,U) and r(s, y,U[{x}). If cost(p) = min{cost(w) : w(s, t,U)^t 2 V }, then we have cost(r) = min(cost(p) + cost(x, y), cost(q)). This is the well-known triangle comparison of Dijkstra’s algorithm.
Afiliacja: Jing-Chao Chen - Donghua University Shanghai
Yatsuka Nakamura - Shinshu University Nagano
URI: http://hdl.handle.net/11320/21543
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 2

Pliki w tej pozycji:
Plik Opis RozmiarFormat 
The_Underlying_Principle_of_Dijkstra's_Shortest_Path_Algorithm.pdf95,37 kBAdobe PDFOtwórz
Pokaż pełny widok rekordu Zobacz statystyki


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