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 | Rozmiar | Format | |
|---|---|---|---|---|
| The_Underlying_Principle_of_Dijkstra's_Shortest_Path_Algorithm.pdf | 95,37 kB | Adobe PDF | Otwórz |
Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL
