Title :
A new practical algorithm for the shortest path problem
Author :
Liu, Pan ; Miao Huai Kou ; Yu Guo Ping ; Liang, Yin
Author_Institution :
Sch. of Comput. Eng. & Sci., Shanghai Univ., Shanghai
Abstract :
A novel Greed-backtracking algorithm (GBA) for the shortest path problem is proposed in this paper. Beginning with triples storage structure to save the data of a weighted directed graph, this paper lays emphasis on a series of greedy strategies and the GBA implementation, there follows the realization of the GBA with Java. In the end, satisfied results are obtained when we applied the GBA to one of the social development projects. Compared with the Dijkstra algorithm, to solve the shortest path between any two points in graph, the average time efficiency of the GBA is increased by 75%.
Keywords :
Java; backtracking; directed graphs; greedy algorithms; mathematics computing; Dijkstra algorithm; Greed-backtracking algorithm; Java; shortest path problem; triples storage structure; weighted directed graph; Automation; Decision support systems; Fiber reinforced plastics; Intelligent control; Shortest path problem; Dijkstra algorithm; Greed-Backtracking algorithm; control strategy; shortest path;
Conference_Titel :
Intelligent Control and Automation, 2008. WCICA 2008. 7th World Congress on
Conference_Location :
Chongqing
Print_ISBN :
978-1-4244-2113-8
Electronic_ISBN :
978-1-4244-2114-5
DOI :
10.1109/WCICA.2008.4594514
