Parallel Shortest Path Algorithm Based on Vertex Cut-set
[1]ZHANG Qinghua,LI Hong,SHEN Wen.Parallel Shortest Path Algorithm Based on Vertex Cut-set[J].Journal of Zhengzhou University (Engineering Science),2012,33(05):125-129.[doi:10.3969/j.issn.1671-6833.2012.05.028]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
33
Number of periods:
2012 05
Page number:
125-129
Column:
Public date:
2012-09-10
- Title:
- Parallel Shortest Path Algorithm Based on Vertex Cut-set
- Keywords:
- cut vertex; shortest path algorithm; Dijkstra algorithm; parallel computing; granular computing
- CLC:
- TP301.6
- DOI:
- 10.3969/j.issn.1671-6833.2012.05.028
- Abstract:
- In this paper, research and analysis on the basis of the l)ijkstra algorithm, the Dijkstra algorithm byintroducing the vertex of cut sets and cut the vertex of idea to improve the Dijkstra algorithm, this method firsvertex eut-set or cut vertex to the original problem is decomposed into multiple sub-graph, then the shortes!path on each sub-graph parallel to the shortest path of the original problem , and finally obtained by the vertexcut-set or cut vertex, which reduces the time complexity of the algorithm and improves the efficieney of the al-gorithm.
- References:
- -
- Similar References:
Memo
-
Last Update:
1900-01-01