| 19 | } |
| 20 | |
| 21 | private double bfs(Map<String, List<Pair<String, Double>>> adj, String src, String target) { |
| 22 | if (!adj.containsKey(src) || !adj.containsKey(target)) { |
| 23 | return -1.0; |
| 24 | } |
| 25 | ArrayDeque<Pair<String, Double>> queue = new ArrayDeque<>(); |
| 26 | Set<String> visited = new HashSet<>(); |
| 27 | queue.addLast(new Pair<>(src, 1.0)); |
| 28 | visited.add(src); |
| 29 | while (!queue.isEmpty()) { |
| 30 | Pair<String, Double> item = queue.pollFirst(); |
| 31 | String node = item.getKey(); |
| 32 | Double curWeight = item.getValue(); |
| 33 | if (node.equals(target)) { |
| 34 | return curWeight; |
| 35 | } |
| 36 | for (Pair<String, Double> neighbor : adj.get(node)) { |
| 37 | String nextNode = neighbor.getKey(); |
| 38 | Double weight = neighbor.getValue(); |
| 39 | if (!visited.contains(nextNode)) { |
| 40 | queue.addLast(new Pair<>(nextNode, curWeight * weight)); |
| 41 | visited.add(nextNode); |
| 42 | } |
| 43 | } |
| 44 | } |
| 45 | return -1.0; |
| 46 | } |
| 47 | } |