网络中短路径的Z算法

Z-Algorithm of Short-path in Network

讨论网络中结点间路径的问题是图论中的基本问题之一 ,而求其中任两结点间的最短路径已有一些方法 ,也可采用延长算法 ,即求出两点间的所有路径 ,算出其路径权值 ,从而求得最短路径。最短路径在实际中有着广泛的应用。在实际中有一些求最优的问题 ,可化为网络中最短路径问题 ,从而得到最优的第一方案。本文提出将任两结点间的不同路径按其权值分成不同阶短路径的概念 ,并基于 Dijkstra算法和路径延长算法 ,给出根据给定的阶值 λ,求相应的 λ阶短路径 Z算法 ,可同时获得最优的第一方案、第二方案、…、第 λ方案。算法简单 ,便于手算 。

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.