Software Engineering White Papers
Point-to-Point Shortest Path Algorithms With Preprocessing
Overview This is a survey of some recent results on point-to-point shortest path algorithms. This classical optimization problem received a lot of attention lately and significant progress has been made. After an overview of classical results, it studies recent heuristics that solve the problem while examining only a small portion of the input graph; the graph can be very big. Note that the algorithms the paper discusses find exact shortest paths. These algorithms are heuristic because they perform well only on some graph classes. While their performance has been good in experimental studies, no theoretical bounds are known to support the experimental observations. Most of these algorithms have been motivated by finding paths in large road networks.
| Publisher | Microsoft | File Format | |
|---|---|---|---|
| Date Published | May 2007 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful?
White Paper RSS
Download
Register
