Several variations exist of the shortest path problem depending on the type of the graph. The most common problems are the shortest path problem between two points and between every pair of points (the so called multiterminal minimal path problem). Beside this several other variations are known. One of them is the shortest path in a network having gains, the time dependent path, the shortest path in a network, where the travelling time depends on the actual traffic flow. In this paper a powerful algorithm is presented in large scale, sparse network. In long term road network planning problem sometimes the size of the network is very large - about hundred thousand. The network is usually sparse, one point is connected with average 3 or 4 points. It will be shown that the presented algorithm in this case is much more powerful. © 2012 IEEE.