DocumentCode
2397742
Title
A shortest path algorithm based on hierarchical graph model
Author
Yimin, Wu ; Jianmin, Xu ; Yucong, Hu ; Qinghong, Yang
Author_Institution
Coll. of Comput. Sci. & Eng., South China Univ. of Technol., Guangzhou, China
Volume
2
fYear
2003
fDate
12-15 Oct. 2003
Firstpage
1511
Abstract
This paper discusses a new algorithm for the shortest path founding based on hierarchical graphs. It plots out a flat graph into some sub-graphs, which are abstracted as a high-level graph. The calculation for the shortest path founding begins at the high-level graph. This method shrinks the searching range of the shortest path and reduces the time spending of calculating it. Since the impedance function among sub-graphs can be calculated dynamically, this algorithm can be applied to dynamic traffic inducement system.
Keywords
graph theory; minimisation; road traffic; dynamic traffic inducement system; flat graph; hierarchical graphs; high-level graph; impedance function; shortest path algorithm; subgraphs; urban traffic; Cities and towns; Computer science; Educational institutions; Heuristic algorithms; Impedance; Information systems; Navigation;
fLanguage
English
Publisher
ieee
Conference_Titel
Intelligent Transportation Systems, 2003. Proceedings. 2003 IEEE
Print_ISBN
0-7803-8125-4
Type
conf
DOI
10.1109/ITSC.2003.1252736
Filename
1252736
Link To Document