Abstract: By introducing the concept of cut point and point cut set, which are the important part of graph theory, this paper combines the algorithm of finding cut point and point cut set with the classical Dijkstra algorithm to form an improved parallel algorithm. The application of the improved parallel algorithm is also given. It provides a theoretical basis for finding the shortest path of undirected graph, and improves the routing algorithm in the routing protocol OSPF, which reduces the time complexity of the algorithm.

Key words: Cut point, Point cut set, Dijkstra algorithm, Routing selection algorithm