This is a collection of notes I’m taking on the implementation of routing algorithms in Merge.
Multipath Network Properties
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
l3 however this does not represent the best path. Alternatively chosing
l4 has an equal cost, so both paths are viable.