Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static int findNumberOfRoutesWithDistance(final Graph graph, final int from, final int to,
- final short maxDistance) {
- Queue<NodeInQueue> queue = new LinkedList<NodeInQueue>();
- queue.add(new NodeInQueue(from, 0));
- int[][] dp = new int[graph.getVertexes().size()][maxDistance + 1];
- while (!queue.isEmpty()) {
- NodeInQueue node = queue.poll();
- final List<EndEdge> fromNeighbours = graph.getFromNeighbours(node.getVertex());
- System.out.println(node.getVertex() + ":" + node.getDistance());
- for (EndEdge endEdge : fromNeighbours) {
- if (endEdge.getCost() + node.getDistance() <= maxDistance) {
- NodeInQueue newNode = new NodeInQueue(endEdge.getVertex(), endEdge.getCost() + node.getDistance());
- dp[newNode.getVertex()][newNode.getDistance()] +=
- dp[node.getVertex()][node.getDistance()] == 0 && node.getVertex() == from
- ? 1 : dp[node.getVertex()][node.getDistance()];
- queue.offer(newNode);
- }
- }
- }
- int result = 0;
- for (int distance = 0; distance < maxDistance; distance++) {
- result += dp[to][distance];
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement