Optimal-path finding techniques are used when a least-cost path between two nodes in a network must be found. The two nodes are called origin and destination. The aim is to find a sequence of connected lines to traverse from the origin to the destination at the lowest possible cost.
In Optimal-path finding, the cost function can be simple: for instance, it can be defined as the total length of all lines of the path. The cost function can also be more elaborate and take into account not only length of the lines but also their capacity, maximum transmission (travel) rate and other line characteristics, for instance to obtain a reasonable approximation of travel time. There can even be cases in which the nodes visited add to the cost of the path as well. These may be called turning costs, which are defined in a separate turning-cost table for each node, indicating the cost of turning at the node when entering from one line and continuing on another. This is illustrated in Figure 1 of the examples.
Problems related to optimal-path finding may require ordered optimal path finding or unordered optimal-path finding. Both have as an extra requirement that a number of additional nodes need to be visited along the path. In ordered optimal-path finding, the sequence in which these extra nodes are visited matters; in unordered optimal-path finding it does not.