Dijkstra's algorithm vs transit algorithm

• Main Author: Chua, Esther Yizhen.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2011
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/43895
• Institution: Nanyang Technological University

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.