Transactions

Path Finding

Naive approach

Follow shortest path. If not enough available credit, follow next shortest path, etc.

More sophisticated approach

Makes tradeoffs between path length and number of overall forking subpaths to reduce search time.

At the current node, for neighbouring node retrieve:

distance to target
available credit in that direction

Choose set of forking directions that minimizes:

number of forks * sum over all forks(avail. credit * distance to target)

Perform depth-first search down each forked subpath, ordered with the following caveat:

When a forked subpath turns out to have less than the available credit of the first step, return to where that path forked and recalculate with the new reduced available credit for that direction, but using the distance remaining to the target on that path (since if we're close, it will be faster to just finish what we started).

Finding subsequent pathsets

A client may request another pathset be found in order to compare pathset costs. Maybe a way to do this is to introduce some randomness into the path-finding after the first pathset is found.

It may be a good idea to limit the number of pathset queries per payment or per unit time, or to charge per query over a certain point, to prevent undue speculation on pathset prices. Better optimizing for pathset cost could be a future feature (see optimization).