Generic Dijkstra
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917306302464000 |
|---|---|
| author | Szcześniak, Ireneusz Woźna-Szcześniak, Bożena Olszewski, Ireneusz |
| author_facet | Szcześniak, Ireneusz Woźna-Szcześniak, Bożena Olszewski, Ireneusz |
| contents | The recently-proposed generic Dijkstra algorithm finds shortest paths in networks with continuous and contiguous resources. While the algorithm was proposed in the context of optical networks (and is applicable to other networks with finite and discrete resources), we present the stated problem in a broader algorithmic setting of the greedy approach. The algorithm was published without a proof of correctness, and with a minor shortcoming. We provide that missing proof and offer a correction to the shortcoming. To prove the algorithm correct, we generalize the greedy approach and the Bellman principle of optimality to algebraic structures with a partial ordering. By analyzing the size of the search space in the worst-case, we argue the stated problem is tractable. Thus we definitely answer a long-standing fundamental question of whether we can efficiently find a shortest path in a network with discrete resources subject to the continuity and contiguity constraints: yes, we can. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_13547 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Generic Dijkstra Szcześniak, Ireneusz Woźna-Szcześniak, Bożena Olszewski, Ireneusz Networking and Internet Architecture Data Structures and Algorithms The recently-proposed generic Dijkstra algorithm finds shortest paths in networks with continuous and contiguous resources. While the algorithm was proposed in the context of optical networks (and is applicable to other networks with finite and discrete resources), we present the stated problem in a broader algorithmic setting of the greedy approach. The algorithm was published without a proof of correctness, and with a minor shortcoming. We provide that missing proof and offer a correction to the shortcoming. To prove the algorithm correct, we generalize the greedy approach and the Bellman principle of optimality to algebraic structures with a partial ordering. By analyzing the size of the search space in the worst-case, we argue the stated problem is tractable. Thus we definitely answer a long-standing fundamental question of whether we can efficiently find a shortest path in a network with discrete resources subject to the continuity and contiguity constraints: yes, we can. |
| title | Generic Dijkstra |
| topic | Networking and Internet Architecture Data Structures and Algorithms |
| url | https://arxiv.org/abs/2204.13547 |