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

fYear

2008

fDate

25-27 June 2008

Firstpage

4120

Lastpage

4122

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/WCICA.2008.4594514

Filename

4594514