b'@article{BMST03,'b'\nTITLE = {A Heuristic for Dijkstra\'s Algorithm With Many Targets and its Use in Weighted Matching Algorithms},\nAUTHOR = {Bast, Holger and Mehlhorn, Kurt and Sch{\\"a}fer, Guido and Tamaki, Hisao},\nLANGUAGE = {eng},\nLOCALID = {Local-ID: C1256428004B93B8-6EE356D1B824CE83C1256D03005D49A1-BMST03},\nYEAR = {2003},\nDATE = {2003},\nABSTRACT = {We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to compute a shortest path from $s$ to a node in $T$. Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with $n$ nodes on each side reduces to $n$ SSMTSP problems, where the number of targets varies between $n$ and $1$. The SSMTSP problem can be solved by Dijkstra\'s algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.},\nJOURNAL = {Algorithmica},\nVOLUME = {36},\nPAGES = {75--88},\n}\n'