Contraction Hierarchies

Date
2014
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Tripod URL
Identifier
Abstract
Optimization of route planning is essential to everyday tasks such as planning trips and traffic simulation. In order to optimize routes in large graphs such as transportation networks, an algorithm must be able to quickly find the shortest path from some source to a specified destination. The contraction hierarchy algorithm is a proposed solution to optimization of route planning. This algorithm has two stages: the first stage consists of ordering the nodes by some importance and removing nodes according to their importance to create a graph in which the shortest paths between nodes are preserved. The second stage is the query in which a shortest path is calculated using a bidirectional Dijkstra search.
Description
Citation
Collections