-
Notifications
You must be signed in to change notification settings - Fork 18
Expand file tree
/
Copy pathRelax.java
More file actions
28 lines (22 loc) · 1.09 KB
/
Relax.java
File metadata and controls
28 lines (22 loc) · 1.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 <V, W, E extends DirectedEdge<V>> boolean relax(MutableMap<V, InfinitableNumber<W>> distance, MutableMap<V, E> previous, E edge, Function<E, W> weightFunction, InfinitableAddableNumberSystem<W> ns) {
InfinitableNumber<W> fromDistance = distance.get(edge.from());
if (fromDistance.isInfinity())
return false;
InfinitableNumber<W> weight = InfinitableNumber.getFiniteInstance(weightFunction.apply(edge));
InfinitableNumber<W> oldDistance = distance.get(edge.to());
InfinitableNumber<W> 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;
}
}