ali Nourollah - Department of Electrical and Computer Engineering of Shahid Rajaee Teacher Training University
elnaz pashaei - Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
elham pashaei - Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
mohammad reza meybodi - Department of IT & Computer Engineering, Amirkabir University of Technology,

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.

Steiner Tree problem- heuristic algorithm- SPH algorithm