Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/43895
Title: Dijkstra's algorithm vs transit algorithm
Authors: Chua, Esther Yizhen.
Keywords: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
Issue Date: 2011
Abstract: Shortest path problem is a problem that is relevant to a wide range of applications like traffic simulation and network routing. These applications play a huge part in our daily lives thus there is a need to explore algorithms which are faster and more efficient. This project explores and implements Dijkstra’s algorithm and Transit algorithm. Dijkstra’s algorithm is an algorithm that computes the shortest path between two nodes in a graph whose path costs are positive by iteratively visiting all the nodes that are closer to the source than the destination before eventually reaching the destination. Transit algorithm makes use of transit nodes as a mean to pre-process a road network where transit nodes are a set of nodes with the property that every non-local shortest path passes through at least one of these nodes. A path is deemed as non-local if its source and destination are more than 4 grid cells apart. Computation of the length of the shortest paths between each pair of transit nodes and between each node in the graph and its neighboring transit nodes are done thus allowing non-local shortest path queries to be answered in an extremely fast manner by combining information from a small number of lookup in a table. Dijkstra’s algorithm, on average will take seconds for a random query while Transit algorithm is expected to have a worst case query processing time of about 10 microseconds for 99% of the queries on United States network which has around 24 million nodes and 29 million edges.
URI: http://hdl.handle.net/10356/43895
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
SCE10-0218.pdf
  Restricted Access
1.3 MBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.