Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

Stefan Hougardy, Jannik Silvanus, Jens Vygen

We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We a…