Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jul 29th, 2012  |  syntax: None  |  size: 3.12 KB  |  hits: 9  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package ua.edu.lnu.pif.ucs;
  2.  
  3. import java.util.Arrays;
  4. import java.util.HashSet;
  5. import java.util.List;
  6. import java.util.Map.Entry;
  7. import java.util.Set;
  8. import java.util.TreeMap;
  9.  
  10. /**
  11.  * Hello world!
  12.  *
  13.  */
  14. public class App {
  15.  
  16.     public static void main(String[] args) {
  17.         Node start1 = new Node("1");
  18.         Node start2 = new Node("2");
  19.         Node start3 = new Node("3");
  20.         Node start4 = new Node("4");
  21.         Node start5 = new Node("5");
  22.         Node start6 = new Node("6");
  23.         Node start7 = new Node("7");
  24.         Node start8 = new Node("8");
  25.         Node start9 = new Node("9");
  26.         Node start10 = new Node("10");
  27.         Node start11 = new Node("11");
  28.         Node start12 = new Node("12");
  29.         Node start13 = new Node("13");
  30.        
  31.         connectNodes(start1, start2, 75);
  32.         connectNodes(start1, start4, 140);
  33.         connectNodes(start1, start5, 118);
  34.         connectNodes(start2, start3, 71);
  35.         connectNodes(start3, start4, 151);
  36.         connectNodes(start4, start12, 99);
  37.         connectNodes(start4, start9, 80);
  38.         connectNodes(start5, start6, 111);
  39.         connectNodes(start6, start7, 70);
  40.         connectNodes(start7, start8, 75);
  41.         connectNodes(start8, start10, 120);
  42.         connectNodes(start9, start10, 146);
  43.         connectNodes(start9, start11, 97);
  44.         connectNodes(start10, start11, 138);
  45.         connectNodes(start11, start13, 101);
  46.         connectNodes(start12, start13, 211);
  47.  
  48.         System.out.println(findPath(start1, start13));
  49.     }
  50.    
  51.     public static List<Node> findPath(Node start, Node finish) {
  52.         TreeMap<Integer, Node> frontier = new TreeMap<Integer, Node>();
  53.         Set<Node> explored  = new HashSet<Node>();
  54.        
  55.         frontier.put(0, start);
  56.         while(!frontier.isEmpty()) {
  57.             System.out.println(frontier);
  58. //            if (frontier.isEmpty()) {
  59. //                throw new IllegalStateException("empty frontier");
  60. //            }
  61.             Entry<Integer, Node> firstEntry = frontier.pollFirstEntry();
  62.             Node closest = firstEntry.getValue();
  63.             System.out.println(firstEntry.getKey() + " " + firstEntry.getValue());
  64.             if (finish.equals(closest)) {
  65.                 System.out.println("FINISH!!!!");
  66.                 System.out.println(firstEntry.getKey() + " " + firstEntry.getValue());
  67.                 return Arrays.asList(new Node[]{closest});
  68.             }
  69.             explored.add(closest);
  70.            
  71.             for (Entry<Integer, Node> entry : closest.getChildren().entrySet()) {
  72.                 if (!explored.contains(entry.getValue())) {
  73.                     frontier.put(firstEntry.getKey()+entry.getKey(), entry.getValue());
  74.                 }
  75.             }
  76.         }
  77.        
  78.         return null;
  79.     }
  80.    
  81.     private static void connectNodes(Node node1, Node node2, int dist) {
  82.         node1.addEdge(node2, dist);
  83.         node2.addEdge(node1, dist);
  84.     }
  85.    
  86.     private static void printGraph(Node start) {
  87.         System.out.println(start);
  88. //        for (Node node : start.getChildren().keySet()) {
  89. //            if (node.equals(start)) {
  90. //                printGraph(node);
  91. //            }
  92. //        }
  93.     }
  94. }
create a new version of this paste RAW Paste Data