Att beräkna den kortaste vägen mellan två givna platser i ett vägnät är ett viktigt problem som hittar tillämpningar i olika karttjänster och kommersiella navigationsprodukter. De senaste lösningarna för problemet kan delas in i två kategorier: rumslig-sammanhållning-baserade metoder och vertex-vikt-baserade metoder. De två teknikkategorierna har dock inte systematiskt jämförts inom samma experimentella ram, eftersom de har utvecklats från två oberoende forskningslinjer som inte hänvisar till varandra. Detta gör det svårt för en utövare att bestämma vilken teknik som ska användas för en specifik tillämpning. Dessutom är den experimentella utvärderingen av den befintliga tekniken, såsom den presenterades i tidigare arbeten, otillräcklig i flera avseenden. Vissa metoder testades endast på små vägnät med upp till hundra tusen hörn; vissa metoder utvärderades med hjälp av distansfrågor (i stället för kortaste sökvägar), nämligen frågor som bara ber om längden på den kortaste vägen; en toppmodern teknik undersöktes baserat på ett felaktigt genomförande som ledde till felaktiga frågeresultat. För att ta itu med ovanstående frågor presenteras i detta dokument en omfattande jämförelse av de mest avancerade rumslig-sammanhållningsbaserade och vertex-vikt-baserade tillvägagångssätten. Med hjälp av en mängd olika verkliga vägnät med upp till tjugo miljoner hörn, utvärderade vi varje teknik i termer av dess förbehandlingstid, rymdförbrukning och frågeeffektivitet (för både kortaste väg och avstånd frågor). Våra experimentella resultat avslöjar egenskaperna hos olika tekniker, utifrån vilka vi ger riktlinjer för val av lämpliga metoder för olika scenarier.
Kortaste väg- och distansfrågor på vägnät har utvärderats experimentellt av Wu et al. Hoppa över det.
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation
{'venue': 'Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 5, pp. 406-417 (2012)', 'journal': None, 'mag_field_of_study': ['Computer Science']}