title: Graph Tour with Uniform Cost Search in Java
body: <p>I'm new to this site, so hopefully you guys don't mind helping a nub.</p>
  
  <p>Anyway, I've been asked to write code to find the shortest cost of a graph tour on a particular graph, whose details are read in from file. The graph is shown below:</p>
  
  <p><a href="http://img339.imageshack.us/img339/8907/graphr.jpg" rel="nofollow noreferrer">http://img339.imageshack.us/img339/8907/graphr.jpg</a></p>
  
  <p>This is for an Artificial Intelligence class, so I'm expected to use a decent enough search method (brute force has been allowed, but not for full marks).</p>
  
  <p>I've been reading, and I think that what I'm looking for is an A* search with constant heuristic value, which I believe is a uniform cost search. I'm having trouble wrapping my head around how to apply this in Java.</p>
  
  <p>Basically, here's what I have:</p>
  
  <p>Vertex class -</p>
  
  <pre><code>ArrayList&lt;Edge&gt; adjacencies;
  String name;
  int costToThis;
  </code></pre>
  
  <p>Edge class -</p>
  
  <pre><code>final Vertex target;
  public final int weight;
  </code></pre>
  
  <p>Now at the moment, I'm struggling to work out how to apply the uniform cost notion to my desired goal path. Basically I have to start on a particular node, visit all other nodes, and end on that same node, with the lowest cost.</p>
  
  <p>As I understand it, I could use a PriorityQueue to store all of my travelled paths, but I can't wrap my head around how I show the goal state as the starting node with all other nodes visited.</p>
  
  <p>Here's what I have so far, which is pretty far off the mark:</p>
  
  <pre><code>public static void visitNode(Vertex vertex) {
        ArrayList&lt;Edge&gt; firstEdges = vertex.getAdjacencies();
        for(Edge e : firstEdges) {
           e.target.costToThis = e.weight + vertex.costToThis;
           queue.add(e.target);
        }
        Vertex next = queue.remove();
        visitNode(next);
     }
  </code></pre>
  
  <p>Initially this takes the starting node, then recursively visits the first node in the PriorityQueue (the path with the next lowest cost).</p>
  
  <p>My problem is basically, how do I stop my program from following a path specified in the queue if that path is at the goal state? The queue currently stores Vertex objects, but in my mind this isn't going to work as I can't store whether other vertices have been visited inside a Vertex object.</p>
  
  <p>Help is much appreciated!
  Josh</p>
  
  <p><strong>EDIT: I should mention that paths previously visited may be visited again. In the case I provided this isn't beneficial, but there may be a case where visiting a node previously visited to get to another node would lead to a shorter path (I think). So I can't just do it based on nodes already visited (this was my first thought too)</strong></p>