# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### A Heuristic for Dijkstra's Algorithm With Many Targets and its Use in Weighted Matching Algorithms

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K., & Schäfer, G. (2001). A Heuristic for Dijkstra's Algorithm With Many
Targets and its Use in Weighted Matching Algorithms. In *Proceedings of the 9th Annual European Symposium
on Algorithms (ESA-01)* (pp. 242-253). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-314B-6

##### Abstract

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 10 was achieved.
We also present a partial analysis that gives some theoretical support for our
experimental findings.