非表示:
キーワード:
-
要旨:
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.
