An Improved Steiner Tree Algorithm in Graph

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum weight subtree spanning a given subset of (terminal) nodes of the original graph, which it is NP-complete. In this paper, we first review one of the existing algorithms for solving the Steiner problem in graphs, Shortest Path Heuristic algorithm, then presenting a new heuristic algorithm ISPH to improve it. We describe our algorithm and its computational results. It is shown that our algorithm can effectively improve the performance on SPH.