Advertisement
Guest User

graph problem

a guest
Aug 28th, 2014
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.33 KB | None | 0 0
  1.     public static int findNumberOfRoutesWithDistance(final Graph graph, final int from, final int to,
  2.             final short maxDistance) {
  3.  
  4.         Queue<NodeInQueue> queue = new LinkedList<NodeInQueue>();
  5.  
  6.         queue.add(new NodeInQueue(from, 0));
  7.  
  8.         int[][] dp = new int[graph.getVertexes().size()][maxDistance + 1];
  9.  
  10.         while (!queue.isEmpty()) {
  11.             NodeInQueue node = queue.poll();
  12.             final List<EndEdge> fromNeighbours = graph.getFromNeighbours(node.getVertex());
  13.  
  14.             System.out.println(node.getVertex() + ":" + node.getDistance());
  15.  
  16.             for (EndEdge endEdge : fromNeighbours) {
  17.                 if (endEdge.getCost() + node.getDistance() <= maxDistance) {
  18.                     NodeInQueue newNode = new NodeInQueue(endEdge.getVertex(), endEdge.getCost() + node.getDistance());
  19.                     dp[newNode.getVertex()][newNode.getDistance()] +=
  20.                         dp[node.getVertex()][node.getDistance()] == 0 && node.getVertex() == from
  21.                         ? 1 : dp[node.getVertex()][node.getDistance()];
  22.                     queue.offer(newNode);
  23.                 }
  24.             }
  25.         }
  26.  
  27.         int result = 0;
  28.  
  29.         for (int distance = 0; distance < maxDistance; distance++) {
  30.             result += dp[to][distance];
  31.         }
  32.  
  33.         return result;
  34.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement