s-t paths using the min-sum algorithm
Nicholas Ruozzi, Sekhar Tatikonda · 2008
Solving the distributed shortest path problem has important applications in the theory of distributed systems, most notably routing. In this paper, we provide and prove the convergence of a min-sum algorithm to compute the shortest path between two nodes in a graph with positive edge weights. Unlike the standard distributed shortest path algorithms, the rate of convergence depends on the weight of the minimal path and not necessarily the number of nodes in the network.