| 摘要 |
This invention concerns a method for providing non-looping routing paths in a network from a begin vertex to a destination vertex. Further, the invention concerns a routing device. A method for providing non-looping routing paths in a network from a begin vertex to a destination vertex is disclosed. The network has at least two vertices and at least two edges, the at least two vertices and the at least two edges defining a graph G and the edges of the Graph G having associated costs. The method comprises the steps of: a) Defining the begin vertex; b) Providing an empty shortest path vertices collection S; c) Finding a vertex with the lowest costs that is not in S; d) Forwarding on outgoing edges of the lowest cost vertex the paths of its list of path to its neighbouring vertex/vertices; e) Adding the forwarded paths to the path lists of each neighbouring vertex, respectively; f) Detecting looping paths and delete looping path from the path lists of the neighbouring vertices; g) Adding the lowest cost vertex to S; and h) Repeating steps c), d), e), f) and g). |
