package org.psjava.algo; import org.psjava.ds.graph.DirectedEdge; import org.psjava.ds.map.MutableMap; import org.psjava.ds.numbersystrem.InfinitableAddableNumberSystem; import org.psjava.ds.numbersystrem.InfinitableNumber; import java.util.function.Function; public class Relax { public static > boolean relax(MutableMap> distance, MutableMap previous, E edge, Function weightFunction, InfinitableAddableNumberSystem ns) { InfinitableNumber fromDistance = distance.get(edge.from()); if (fromDistance.isInfinity()) return false; InfinitableNumber weight = InfinitableNumber.getFiniteInstance(weightFunction.apply(edge)); InfinitableNumber oldDistance = distance.get(edge.to()); InfinitableNumber newDistance = ns.add(fromDistance, weight); if (ns.compare(oldDistance, newDistance) > 0) { distance.replace(edge.to(), newDistance); previous.addOrReplace(edge.to(), edge); return true; } return false; } }