Scientific WorkFlows (SWFs) play significant roles in scientific research and engineering simulation, which are often data intensive and has complex data dependencies. The storage of massive intermediate datasets has great impacts on the performance and the quality of service of a SWF system, which has become a difficult and complex task. Through analyzing the cost transitive tournament shortest path (CTT-SP)-based algorithm proposed for the intermediate data storage in SWF systems, the disadvantage of the CTT-SP algorithm over its sensitivity to the main branches can be found. We proposed an improved CTT-SP algorithm based on the critical path method (CPM), aiming at reducing the sensitivity of the main branch and improving the performance of the algorithm. By adding the generation information of the datasets on the arrows, the data dependency graph of a SWF can be converted to an activity on arrow (AOA) net. Then, the critical path of the AOA net is used to be the main branch of the CTT-SP algorithm, which can reduce the impacts of the main branch and keep the quality of service of the SWF systems. Experiments are designed to test the impacts of the main branches and the performance of the improved CTT-SP algorithms. The results show the significant impacts of the main branches on the performance of the CTT-SP algorithm and the effectiveness of the CPM on improving the performance of the CTT-SP algorithm. Comparison results demonstrate the positiveness and effectiveness of the improved CTT-SP algorithm.