Abstract: In order to solve the problem of the shortest path with weight under complex network conditions，a tabu search algorithm based on compression graphs was proposed. With the constraintbased graph compression algorithm，the weighted shortest path problem under complex constraints was transformed into travelling salesman problem（TSP），and the optimization of the tabu search algorithm was used to solve the weighted shortest path problem under complex constraints. The simulation results showed that the tabu search algorithm based on compression graph had the advantages of fast solution，low time complexity，fast convergence，and insensitivity to graph scale and constraint conditions.

Key words: weighted shortest path under constraints, pruning, travelling salesman problem, tabu search algorithm