Shortest path determination processes for use in modeling systems and communications networks

摘要

Methods for operating a modeling system and/or a communications network, using a computer assisted process, are described, which transform a first set of signals, including (a) signals representing a given linear network defined in terms of a set of node identification signals, (b) a set of weighted/directed edge signals each of which identify the weight, direction and the pair of nodes in the network interconnected via a given edge, and (c) signals representing arbitrarily specified start and target nodes in the network, into a second set of signals indicating the shortest path in the network between the start and target nodes. The processes contemplated by the invention perform the aforementioned transformation by incrementally creating an array of node identification signals directly from the first set of signals. No starting matrix (or sparse matrix), as required by prior art processes, needs to be created or stored. Furthermore, the processes contemplated by the invention build the array as a function of array contents (as the array is being incrementally created). As a result of these features, it is not necessary to visit every node in the network to determine the shortest path between two nodes, and the shortest path determination can be made in a manner which conserves computing resources.