fork(4) download 
  1. import java.util.PriorityQueue;
  2. import java.util.HashSet;
  3. import java.util.Set;
  4. import java.util.Collections;
  5. import java.util.List;
  6. import java.util.ArrayList;
  7. import java.util.Comparator;
  8.  
  9. //diff between uniform cost search and dijkstra algo is that UCS has a goal
  10.  
  11. class UniformCostSearchAlgo{
  12.     public static void main(String[] args){
  13.  
  14.         //initialize the graph base on the Romania map
  15.         Node n1 = new Node("Arad");
  16.         Node n2 = new Node("Zerind");
  17.         Node n3 = new Node("Oradea");
  18.         Node n4 = new Node("Sibiu");
  19.         Node n5 = new Node("Fagaras");
  20.         Node n6 = new Node("Rimnicu Vilcea");
  21.         Node n7 = new Node("Pitesti");
  22.         Node n8 = new Node("Timisoara");
  23.         Node n9 = new Node("Lugoj");
  24.         Node n10 = new Node("Mehadia");
  25.         Node n11 = new Node("Drobeta");
  26.         Node n12 = new Node("Craiova");
  27.         Node n13 = new Node("Bucharest");
  28.         Node n14 = new Node("Giurgiu");
  29.  
  30.         //initialize the edges
  31.         n1.adjacencies = new Edge[]{
  32.             new Edge(n2,75),
  33.             new Edge(n4,140),
  34.             new Edge(n8,118)
  35.         };
  36.  
  37.         n2.adjacencies = new Edge[]{
  38.             new Edge(n1,75),
  39.             new Edge(n3,71)
  40.         };
  41.  
  42.         n3.adjacencies = new Edge[]{
  43.             new Edge(n2,71),
  44.             new Edge(n4,151)
  45.         };
  46.  
  47.         n4.adjacencies = new Edge[]{
  48.             new Edge(n1,140),
  49.             new Edge(n5,99),
  50.             new Edge(n3,151),
  51.             new Edge(n6,80),
  52.         };
  53.  
  54.         n5.adjacencies = new Edge[]{
  55.             new Edge(n4,99),
  56.             new Edge(n13,1) // changed cost
  57.         };
  58.  
  59.         n6.adjacencies = new Edge[]{
  60.             new Edge(n4,80),
  61.             new Edge(n7,97),
  62.             new Edge(n12,146)
  63.         };
  64.  
  65.         n7.adjacencies = new Edge[]{
  66.             new Edge(n6,97),
  67.             new Edge(n13,101),
  68.             new Edge(n12,138)
  69.         };
  70.  
  71.         n8.adjacencies = new Edge[]{
  72.             new Edge(n1,118),
  73.             new Edge(n9,111)
  74.         };
  75.  
  76.         n9.adjacencies = new Edge[]{
  77.             new Edge(n8,111),
  78.             new Edge(n10,70)
  79.         };
  80.  
  81.         n10.adjacencies = new Edge[]{
  82.             new Edge(n9,70),
  83.             new Edge(n11,75)
  84.         };
  85.  
  86.         n11.adjacencies = new Edge[]{
  87.             new Edge(n10,75),
  88.             new Edge(n12,120)
  89.         };
  90.  
  91.         n12.adjacencies = new Edge[]{
  92.             new Edge(n11,120),
  93.             new Edge(n6,146),
  94.             new Edge(n7,138)
  95.         };
  96.  
  97.         n13.adjacencies = new Edge[]{
  98.             new Edge(n7,101),
  99.             new Edge(n14,90),
  100.             new Edge(n5,211)
  101.         };
  102.  
  103.         n14.adjacencies = new Edge[]{
  104.             new Edge(n13,90)
  105.         };
  106.  
  107.         UniformCostSearch(n1,n13);
  108.  
  109.         List<Node> path = printPath(n13);
  110.  
  111.         System.out.println("Path: " + path);
  112.  
  113.     }
  114.  
  115.     public static void UniformCostSearch(Node source, Node goal){
  116.  
  117.         source.pathCost = 0;
  118.         PriorityQueue<Node> queue = new PriorityQueue<Node>(20, 
  119.             new Comparator<Node>(){
  120.  
  121.                 //override compare method
  122.                 public int compare(Node i, Node j){
  123.                     if(i.pathCost > j.pathCost){
  124.                         return 1;
  125.                     }
  126.  
  127.                     else if (i.pathCost < j.pathCost){
  128.                         return -1;
  129.                     }
  130.  
  131.                     else{
  132.                         return 0;
  133.                     }
  134.                 }
  135.             }
  136.  
  137.         );
  138.  
  139.         queue.add(source);
  140.         Set<Node> explored = new HashSet<Node>();
  141.         boolean found = false;
  142.  
  143.         //while frontier is not empty
  144.         do{
  145.  
  146.             Node current = queue.poll();
  147.             explored.add(current);
  148.  
  149.  
  150.             if(current.value.equals(goal.value)){
  151.                 found = true;
  152.  
  153.  
  154.             }
  155.  
  156.  
  157.  
  158.  
  159.             for(Edge e: current.adjacencies){
  160.                 Node child = e.target;
  161.                 double cost = e.cost;
  162.                 child.pathCost = current.pathCost + cost;
  163.  
  164.  
  165.  
  166.                 if(!explored.contains(child) && !queue.contains(child)){
  167.  
  168.                     child.parent = current;
  169.                     queue.add(child);
  170.  
  171.                     System.out.println(child);
  172.                     System.out.println(queue);
  173.                     System.out.println();
  174.  
  175.                 }
  176.                 else if((queue.contains(child))&&(child.pathCost>current.pathCost)){
  177.                     child.parent=current;
  178.  
  179.                     // the next two calls decrease the key of the node in the queue
  180.                     queue.remove(child);
  181.                     queue.add(child);
  182.                 }
  183.  
  184.  
  185.             }
  186.         }while(!queue.isEmpty());
  187.  
  188.     }
  189.  
  190.     public static List<Node> printPath(Node target){
  191.         List<Node> path = new ArrayList<Node>();
  192.         for(Node node = target; node!=null; node = node.parent){
  193.             path.add(node);
  194.         }
  195.  
  196.         Collections.reverse(path);
  197.  
  198.         return path;
  199.  
  200.     }
  201.  
  202. }
  203.  
  204. class Node{
  205.  
  206.     public final String value;
  207.     public double pathCost;
  208.     public Edge[] adjacencies;
  209.     public Node parent;
  210.  
  211.     public Node(String val){
  212.  
  213.         value = val;
  214.  
  215.     }
  216.  
  217.     public String toString(){
  218.         return value;
  219.     }
  220.  
  221. }
  222.  
  223. class Edge{
  224.     public final double cost;
  225.     public final Node target;
  226.  
  227.     public Edge(Node targetNode, double costVal){
  228.         cost = costVal;
  229.         target = targetNode;
  230.  
  231.     }
  232. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin 
Standard input is empty
stdout 
Zerind
[Zerind]

Sibiu
[Zerind, Sibiu]

Timisoara
[Zerind, Sibiu, Timisoara]

Oradea
[Timisoara, Sibiu, Oradea]

Lugoj
[Sibiu, Oradea, Lugoj]

Fagaras
[Oradea, Lugoj, Fagaras]

Rimnicu Vilcea
[Rimnicu Vilcea, Lugoj, Oradea, Fagaras]

Pitesti
[Lugoj, Fagaras, Oradea, Pitesti]

Craiova
[Lugoj, Fagaras, Oradea, Pitesti, Craiova]

Mehadia
[Fagaras, Mehadia, Oradea, Craiova, Pitesti]

Bucharest
[Bucharest, Oradea, Pitesti, Craiova, Mehadia]

Giurgiu
[Oradea, Mehadia, Craiova, Pitesti, Giurgiu]

Drobeta
[Giurgiu, Pitesti, Craiova, Drobeta]

Path: [Arad, Sibiu, Fagaras, Bucharest]
https://ideone.com/KCqfXM
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!