Abstrakt. Vi presenterar ett nytt system för att beräkna kortaste vägar på verkliga viktade oriktade grafer i den grundläggande jämförelse-addition modellen. I en effektiv förbehandlingsfas skapar vår algoritm en linjär struktur som underlättar kortaste beräkning av en källa i O(m log α)-tid, där α = α(m, n) är den mycket långsamt växande inverse-Ackermann-funktionen, m antalet kanter och n antalet hörn. Eftersom speciella fall vår algoritm innebär nya gränser på både alla-par och en-källa kortaste vägar problem. Vi löser alla-par problem i O(mn log α (m, n)) tid och, om förhållandet mellan den maximala och minsta kant längder begränsas av n (log n) O (1), Vi kan lösa den enda-källa problemet i O (m + n log n) tid. Båda dessa resultat är teoretiska förbättringar över Dijkstra algoritm, som var den tidigare bäst för verkliga viktade oriktade grafer. Vår algoritm tar det hierarkibaserade tillvägagångssätt som Thorup uppfann.
Den snabbaste APSP algoritmen för glesa oriktade viktade grafer är Pettie och Ramachandran REF och körs i O(mn log α(m, n) tid.
A shortest path algorithm for real-weighted undirected graphs
{'venue': 'in 13th ACMSIAM Symp. on Discrete Algs', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}