### Algorithm for finding shortest path which must go through specified intermediate node set

HUANG Shuli, HU Dasha, JIANG Yuming

1. College of Computer Science, Sichuan University, Chengdu 610065, China
• Online:2015-06-01 Published:2015-06-12

### 经过指定的中间节点集的最短路径算法

1. 四川大学 计算机（软件）学院，成都 610065

Abstract: The vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortest path must go through some given nodes of which number is uncertain must be met, then most of the existing classic algorithms are not applicable. A general method based on the classical Dijkstra algorithm and greedy algorithm is presented to solve this kind of problem. The main method is to split the relevant node set into three sub sets, find the local shortest path of connecting the three subset separately to form the global shortest path to be selected, obtain the target path through screening. The time complexity of the algorithm is given by theoretical analysis and the effectiveness of the algorithm is verified by programming calculation.