f6a673f09493afcd8b129a0bcf1cd5bc-Supplemental.pdf

Then, we show that traditional methods satisfy the semiring assumption and therefore can be solved by the generalized Bellman-Ford algorithm. It should be stressed that the generalized Bellman-Ford algorithm for path problems has been provedin[4],and not acontributionofthis paper. Due to the product definition of path representations, a path of length0 is equal to the multiplication identity 1 q. Similarly, a summation of no path is equal to thesummation identity 0 q. INDICATORis called |V| times, and a single call toINDICATORtakes O(d) time.