Optimal Path Finding

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.

The attentive reader will notice that it is possible to travel on line b in Figure 1, make a U-turn at node N, and return along a to where one came from. The question is whether doing this makes sense in optimal-path finding. After all, to go back to where one came from will only increase the total cost. In fact, there are situations where it is optimal to do so. Suppose it is node M that is connected by line b with node N, and that we actually wanted to travel from M to another node L. The turn at M towards node L coming via another line may be prohibitively expensive, whereas turning towards L at M and returning to M along b may not be so expensive.

An illustration of ordered and unordered path finding types is provided in Figure 2. Here, a path is found from node A to node D, via nodes B and C. Obviously, the length of the path found under non-ordered requirements is at most as long as the one found under ordered requirements. Some GISs provide support for these more complicated path-finding problems.