Optimal path search algorithm which is a killer application of mobile device to utilize location information should consider traffic flows of the roads as well as the distance between a departure and destination. The existing path search algorithms, however, are net able to cope efficiently with the change of the traffic flows. In this paper, we propose a new optimal path search algorithm. The algorithm takes the current flows into consideration in order to reduce the cost to get destination. It decomposes the road network into Fixed Grid to get variable heuristics. We also carry out the experiments with Dijkstra and Ar algorithm in terms of the execution time, the number of node accesses and the accuracy of path. The results obtained from the experimental tests show the proposed algorithm outperforms the others. The algorithm is highly expected to be useful in a advanced telematics systems.