What is the "shortest path heuristic" for the Steiner problem in graphs?
Let G = (V, E) be our graph, and S be the set of vertices that must be in the Steiner tree. Let t be the number of leaves in the optimal Steiner tree.
It seems that Takahashi and Matsuyama's algorithm (1980) is indeed the &quot;shortest path heuristic&quot; since it actually uses shortest-path searches. Starting from a single vertex, it simply grows the tree T by finding the closest vertex v in S \ T that hasn't been added yet, and adding the shortest path from T to v until all vertices have been added, similar to Prim's algorithm for the minimum spanning tree.
The algorithm I cited from Wikipedia, based on the metric closure, is due to Kou, Markowsky and Berman (1981), and boils down to: compute the metric closure, find the minimum spanning tree of the metric closure, turn this back into a subgraph (not necessarily a tree) of the original graph, find the minimum spanning tree of that subgraph, then repeatedly remove leaves that are not in S.
I didn't read Gilbert and Pollak (1968) fully (it's mostly about the geometry of Steiner trees in the plane). I presume they did something similar to Kou et al., but without the final pruning step, which might explain why they only got within a factor 2 from the optimal cost, rather than the 2 - 2/t by Kou et al..
I made some edits to Wikipedia to record all this, and added a summary of an algorithm by Wu, Widmayer and Wong (1986), which is more efficient and also easier to implement than both of the above, while retaining the same optimality bound.