When shortest path algorithm be used in real time road network monitoring system, the time complexity of the algorithm is becoming the bottleneck of the system. the paper proposes a solution to improve the shortest path algorithm. By making use of the k-ary-reverse tree and locality principle, this improved algorithm keeps the data operation, in priority queue, be localized in a small range. So the time complexity of this improved shortest path algorithm is optimized from O(nlog2n) to $$O(k\times n)$$ ; the parameter k denotes the average count of adjacency edges to each vertex, and n denotes the total count of vertexes in the network. Note that, the parameter k mainly depends on the edges density in the network. Generally speaking, the mean value of parameter k is not more than 4 in the road network, i.e. the time complexity of the improved algorithm is optimized from O(nlog2n) to O( n) in the road network. So the paper makes a conclusion that there is a linear correlation between the time complexity and the vertexes count n in the improved algorithm. [ABSTRACT FROM AUTHOR]