I detta dokument, vi anser Dijkstra algoritm för en enda källa enda mål kortaste vägar problem i stora glesa grafer. Målet är att minska svarstiden för online-frågor genom att använda förhandsberäknad information. För resultatet av förbehandlingen erkänner vi som mest linjärt utrymme. Vi antar att en layout av grafen ges. Från denna layout, i förbehandlingen, bestämmer vi för varje kant ett geometriskt objekt som innehåller alla noder som kan nås på en kortaste väg som börjar med den kanten. Baserat på dessa geometriska objekt kan sökytan för onlineberäkning minskas avsevärt. Vi presenterar en omfattande experimentell studie som jämför inverkan av olika typer av objekt. De testdata vi använder är trafiknät, det typiska användningsområdet för detta scenario.
Geometriska behållare REF kräver nodkoordinater och lagra ett enkelt geometriskt objekt som innehåller alla noder som nås via en kortaste väg.
Geometric speed-up techniques for finding shortest paths in large sparse graphs
{'venue': 'IN 11TH EUROPEAN SYMPOSIUM ON ALGORITHMS, VOLUME 2832 OF LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}