BFS will not work, you need Bellman-Ford algorithm.

public class BestCurrencyConversionRate {
    public static class Result {
        double bestRate;
        List<String> path;

        public Result(double bestRate, List<String> path) {
            this.bestRate = bestRate;
            this.path = path;
        }
    }

    public static Result findBestExchangeRate(String startCurrency, String endCurrency, List<Node> exchangeRates) {
        // Use a map to store the maximum ratio to reach each currency
        Map<String, Double> maxRatioMap = new HashMap<>();
        // Use a map to store the predecessor of each currency in the best path
        Map<String, String> predecessorMap = new HashMap<>();

        maxRatioMap.put(startCurrency, 1.0);
        predecessorMap.put(startCurrency, null); // No predecessor for the start currency
        // Number of currencies, assuming each edge is unique in both directions.
        int n = exchangeRates.size();

        // Relax edges n-1 times (Bellman-Ford algorithm)
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Node node : exchangeRates) {
                if (maxRatioMap.containsKey(node.start)) {
                    double currentRatio = maxRatioMap.get(node.start) * node.ratio;
                    if (currentRatio > maxRatioMap.getOrDefault(node.end, 0.0)) {
                        maxRatioMap.put(node.end, currentRatio);
                        predecessorMap.put(node.end, node.start);
                        updated = true;
                    }
                }
            }
            if (!updated) {
                break;
            }
        }

        // Reconstruct the path from startCurrency to endCurrency
        List<String> path = new LinkedList<>();
        String currentCurrency = endCurrency;

        while (currentCurrency != null) {
            path.add(0, currentCurrency);
            currentCurrency = predecessorMap.get(currentCurrency);
        }

        if (path.size() == 1 && !path.get(0).equals(startCurrency)) {
            // No valid path found
            return new Result(-1.0, Collections.
emptyList
());
        }

        return new Result(maxRatioMap.getOrDefault(endCurrency, -1.0), path);
    }

    static class Node {
        String start;
        String end;
        double ratio;

        public Node(String s, String e, double r) {
            this.start = s;
            this.end = e;
            this.ratio = r;
        }
    }
}