diff options
author | mvglasow <michael -at- vonglasow.com> | 2018-10-08 21:54:01 +0200 |
---|---|---|
committer | mvglasow <michael -at- vonglasow.com> | 2018-10-08 21:54:01 +0200 |
commit | 34dd7b4b416fbe4dc6ec036f100e69bae2b00a62 (patch) | |
tree | d4e2a5937ca66ed2e776c641d1f0d7556412fa59 /README.md | |
parent | edf9e62709281ddb118bf55249262c258fdf25e2 (diff) | |
download | navit-34dd7b4b416fbe4dc6ec036f100e69bae2b00a62.tar.gz |
Refactor:core:Documelt LPA* in README.mdtraffic-merge1
Signed-off-by: mvglasow <michael -at- vonglasow.com>
Diffstat (limited to 'README.md')
-rw-r--r-- | README.md | 19 |
1 files changed, 10 insertions, 9 deletions
@@ -77,17 +77,18 @@ Navit reads the current vehicle position: Routing algorithm ================= -Navit uses a Dijkstra algorithm for routing. The routing starts at the -destination by assigning a value to each point directly connected to -destination point. The value represents the estimated time needed to -pass this distance. +Navit uses LPA* (see https://en.wikipedia.org/wiki/Lifelong_Planning_A*), a derivative of the Dijkstra algorithm, for +routing. Routing starts at the destination by assigning a value to each point directly connected to the destination +point. The value represents the estimated time needed to reach the destination from that point. -Now the point with the lowest value is chosen using the Fibonacci -heap and a value is assigned to connected points whos are -unevaluated or whos current value ist greater than the new one. +Now the point with the lowest value is chosen using the Fibonacci heap, and a value is assigned to connected points +which are unevaluated or whose current value is greater than the new one. The search is repeated until the origin is found. -Once the origin is reached, all that needs to be done is to follow the -points with the lowest values to the destination. +Once the origin is reached, all that needs to be done is to follow the points with the lowest values to the +destination. +LPA* is slightly more complex, as it allows partial re-evaluation of the route graph as segment costs change. This is +used by the (still experimental) traffic module, which can process traffic reports and tries to find a way around +traffic problems. Refer to the Wikipedia page for a full description.
\ No newline at end of file |