碩士 / 國立交通大學 / 資訊科學與工程研究所 / 97 / The shortest path problem has been studied for decades, and many efficient algorithms based on Dijkstra's algorithm have been developed. In this thesis, we focus on the road network graphs. Priority queue is an important data structure used in Dijkstra's algorithm. Since the road netwrok graph has low degree, we propose a lazy binary heap as the priority queue. According to our experiments, we reduce 30% to 50% running time on this kind of sparse graphs. Moreover, our implementation has better space efficiency than standard binary heap. Based on the road network, we also study the public transportation system of Taipei City. In this work, we first model it as a graph, then propose a system architecture. Because of the preference of different users, we design different metric functions for different preference. In our experiments, we have tried different metrics and parameters setting.
| Identifer | oai:union.ndltd.org:TW/097NCTU5394131 |
| Date | January 2009 |
| Creators | Lin, Jhih-Yan, 林志晏 |
| Contributors | Tsai, Shi-Chun, 蔡鍚鈞 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | en_US |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 49 |
Page generated in 0.0014 seconds