This is a collection of notes I’m taking on the implementation of routing algorithms in Merge.
Multipath Network Properties
Path counting
The number of distinct paths between any 2 given points on a network, assuming the network is fully connected is the following
the product of the number of routes to the destination at each node in the network. In a non-multipath network this simply decays to 1 as the path to any particulat destination is unique and each node only has a single route. It’s important to note that the routes function must take into account the shortest route to avoid loops. Consider the diagram below
When considering routes to node 11 at f3, clearly one could go through s1 and through f2 instead of directly to l4 or l3 however this does not represent the best path. Alternatively chosing l3 or l4 has an equal cost, so both paths are viable.