Untitled
unknown
java
a month ago
3.5 kB
3
Indexable
public class BacktrackingStrategy implements BestRateFinder { private double findMaxRate(HashMap<String, ArrayList<Edge>> adjList, HashSet<String> visited, String source, String target){ if(Objects.equals(source, target)){ return 1.0; } visited.add(source); double rate = -1.0; for(int i = 0;i<adjList.get(source).size();i++){ if(!visited.contains(adjList.get(source).get(i).target)){ rate = Math.max(rate, adjList.get(source).get(i).rate * findMaxRate(adjList, visited, adjList.get(source).get(i).target, target)); } } visited.remove(source); return rate; } @Override public double findBestRate(ArrayList<Currency> currencies, String source, String target) { HashMap<String, ArrayList<Edge>> adjList = new HashMap<>(); for(Currency curr: currencies){ adjList.putIfAbsent(curr.getSource(), new ArrayList<>()); adjList.putIfAbsent(curr.getTarget(), new ArrayList<>()); adjList.get(curr.getSource()).add(new Edge(curr.getTarget(), curr.getRate())); } HashSet<String> visitedCurrencies = new HashSet<>(); return findMaxRate(adjList, visitedCurrencies, source, target); } } public class BellmanFord implements BestRateFinder { @Override public double findBestRate(ArrayList<Currency> currencies, String source, String target) { HashMap<String, Double> dist = new HashMap<>(); ArrayList<EdgeV2> edges = new ArrayList<>(); for(Currency curr: currencies){ double weight = -Math.log(curr.getRate()); dist.putIfAbsent(curr.getSource(), Double.MAX_VALUE); dist.putIfAbsent(curr.getTarget(), Double.MAX_VALUE); EdgeV2 edge = new EdgeV2(curr.getSource(), curr.getTarget(), weight); edges.add(edge); } dist.put(source, 0.0); int V = dist.size(); for(int i = 0;i<V-1;i++){ for(EdgeV2 curr: edges){ if(dist.get(curr.getSource()) + curr.getWeight() < dist.get(curr.getTarget())){ dist.put(curr.getTarget(), dist.get(curr.getSource()) + curr.getWeight()); } } } return Math.exp(-dist.getOrDefault(target, Double.MAX_VALUE)); } } public interface BestRateFinder { double findBestRate(ArrayList<Currency> currencies, String source, String target); } public class Currency { private String source; private String target; private double rate; public String getSource() { return source; } public String getTarget() { return target; } public double getRate() { return rate; } public Currency(String source, String target, double rate) { this.source = source; this.target = target; this.rate = rate; } } public class EdgeV2 { String source; String target; Double weight; public EdgeV2(String source, String target, Double weight) { this.source = source; this.target = target; this.weight = weight; } public String getSource() { return source; } public String getTarget() { return target; } public Double getWeight() { return weight; } } public class Edge { public String target; public Edge(String target, double rate) { this.target = target; this.rate = rate; } public double rate; }
Editor is loading...
Leave a Comment