Scene Shortest Path Solutions Based on the Breadth First Search


Article Preview

Breadth first search is one of the most convenient traversal methods of a graph, and the shortest path problem of the city map is a kind of traditional data structure problems. It was researched and analyzed that the breadth first search traversing algorithm which adopting the adjacency matrix as its storage structure, in VC++6.0 environment, the shortest path problem of a city map was solved with breadth first search of the graph based on the queue, and its complete program was realized in the machine. Experimental results show that taking the breadth first search to solution city shortest path is an easy to understand and feasible scheme, so it has certain popularize value.



Edited by:

Yanwen Wu




J. H. Wen et al., "Scene Shortest Path Solutions Based on the Breadth First Search", Advanced Materials Research, Vol. 267, pp. 25-29, 2011

Online since:

June 2011




[1] Kuanggui Juan. The application of Breadth-first search algorithm in the interconnection network communication, Qingdao University, a master's degree thesis, 6(2005).

[2] . Wang xingfeng, Jialing. Research on Shortest Path Searching for Urban Traffic Network Based on GIS. Jisuanji yu xiandaihua, 3(2005).

[3] Yang Zhiming. Analysis and implementation of Breadth-first search traversal algorithm of a graph, Agriculture Network Information, 12, 136-137(2009).

[4] . ]. (U.S. ) Davis book, Feng Shun Xi translation. Data Structures and Algorithm Analysis: C language description, Mechanical Industry Press, (2004).

[5] Yan Wei-Min, Wu Weimin. Data structure (C-language version), Tsinghua University Press. 4( 2007).

[6] Wang Xiaodong. A computer algorithm design and analysis (3rd edition), Electronic Industry Press, 5(2007).