Faster Algorithms for the Shortest Path Problem (Classic Reprint)
ISBN: 978-13-322-6076-8
Format: 15.2x22.9cm
Liczba stron: 48
Oprawa: Miękka
Wydanie: 2018 r.
Język: angielski
Dostępność: aktualnie niedostępny
Excerpt from Faster Algorithms for the Shortest Path Problem<br><br>Surprisingly, these two directions have not been very complementary. The algorithms that achieve the best worst-case complexity have generally not been attractive empirically and the algorithms that have performed well in practice have generally failed to have an attractive worst-case bound. In this paper, we present new implementations of Dijkstra's algorithm intended to bridge this gap. Under the assumption that arc lengths are bounded by a polynomial function of n these algorithms achieve the best possible worst-case complexity for all but very sparse graphs and yet are simple enough to be efficient in practice.<br><br>About the Publisher<br><br>Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com<br><br>This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.