Z-Algorithm of Short-path in Network
Zhou Qin · Journal of Nanjing Polytechnic College · 2002
The path between nodes in network is the basic problem in graph theory. There are some methods to get the shortest path between arbitrary two nodes. Also we can use extension algorithm to get all paths between two nodes, then calculate its weight to get the shortest path. Shortest path has extensive application in reality. The problem of the most excellent can be changed to the shortest path in network to get the most excellent and the first scheme. This paper puts forward the concept of different path between arbitrary two nodes dividing into different level short path according to its weight. Based on the Dijkstra algorithm and extension algorithm, according to λ level, the paper evaluates z algorithm of λ level short path, simultaneously gets the most excellent and the first scheme, the second scheme, …, the λ scheme.