Translated Title
Optimization of Dijkstra Shortest Path Algorithm in Indoor Discrete Grid Space
Translated Abstract
This paper put forward an optimization method for Dijkstra shortest path algorithm for discrete grid space for indoor positioning based on RSSI（Received Signal Strength Indicator）fingerprint database.In the method,the shortest paths were calculated separately among different sub-zones and within sub-zone,and the intersection between the shortest path and the sub-zone including the starting or end node obtained to replace the node in sub-zone.Furthermore,with the indoor discrete grid spatial partitioned,network vertexesset,relationship between zones and vertexes confirmed,and the Dijkstra algorithmoptimized,abest shortest path was achieved using PostGIS/pgRouting database.The experiment shows that the optimized method not only gets the correct results,but also improves the efficiency on data storage and computing complexity by about 90%.
Translated Keyword
Dijkstra algorithm
discrete grid space
indoor localization
shortest path
