Graph Problems

  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>public class DijkstraShortestPath

   static class
                    Vertex implements ComparableVertex

  
                    {

       String name;

>        ListEdge adjacencyList = new ArrayList();

       boolean visited;
                    

       Vertex predecessor;

>        int distance = Integer.MAX_VALUE;> >        Vertex(String name)>        {>            this.name = name;>        }

       void addNeighbor(Edge edge)

>        {>            adjacencyList.add(edge); >        }

       @Override

>        public int compareTo(Vertex o)>        {>            return Integer.compare(distance, o.distance);>        }> 

      
                    @Override

       public String toString()
                    

       {

>            return "Vertex{" +>                    "name='" + name + '\'' + >                    '}';>        }>    }

   static class Edge

>    {>        int weight;>        Vertex fromVertex;>        Vertex toVertex;> 

      
                    Edge(int weight, Vertex fromVertex, Vertex toVertex)

>        {>            this.weight = weight; >            this.fromVertex = fromVertex;>            this.toVertex = toVertex;> 

          
                    fromVertex.addNeighbor(this);

       }

   }

> 

   static
                    private void computePathFrom(Vertex sourceVertex)

>    {

      
                    sourceVertex.distance = 0;

>        PriorityQueueVertex pq = new PriorityQueue();

      
                    pq.add(sourceVertex);

      
                    while(!pq.isEmpty())

       {

>            Vertex vertex = pq.poll();>            if(!vertex.visited)>            { >                vertex.visited = true;>                for(Edge edge : vertex.adjacencyList) >                { >                    Vertex targetVertex = edge.toVertex; >                    int distance = vertex.distance + edge.weight;

                  
                    if(targetVertex.distance  distance)

>                    {>                        targetVertex.distance = distance;>                        targetVertex.predecessor = vertex; >                        pq.add(targetVertex);>                    }>                }>            } >        }

   }
                    

>    private static int getShortestPath(Vertex targetVertex, ListVertex result)

   {

>        for(Vertex vertex = targetVertex; vertex != null; vertex = vertex.predecessor)

       {
                    

           result.add(vertex);

>        }>        int distance = result.get(0).distance;>        Collections.reverse(result);>        return distance;>    }

   static int getShortestPath(Vertex fromVertex,
                    Vertex toVertex, ListVertex path)

  
                    {

       computePathFrom(fromVertex);

       return getShortestPath(toVertex, path);
                    

   }

>}

  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()

   Vertex a =
                    new Vertex("A");

   Vertex b = new
                    Vertex("B");

   Vertex c = new
                    Vertex("C");

   Vertex d = new
                    Vertex("D");

   Vertex e = new
                    Vertex("E");

   Vertex f = new
                    Vertex("F");

   Vertex g = new
                    Vertex("G");

   Vertex h = new
                    Vertex("H");

   new Edge(5, a, b);
                    

   new Edge(8, a, h);

>    new Edge(9, a, e);>    new Edge(5, e, h);>    new Edge(4, e, f); >    new Edge(20, e, g);>    new Edge(15, b, d);>    new Edge(12, b, c);>    new Edge(4, b, h);>    new Edge(6, h, f);>    new Edge(7, h, c);>    new Edge(1, f, c);>    new Edge(13, f, g);>    new Edge(9, d, g); >    new Edge(11, c, g);>    ListVertex path = new ArrayList();pre data-role="codeBlock" data-info="js" class="language-javascript">    int distance = getShortestPath(a, g, path);>    boolean check = distance == 25;>    if(!check)>    {>        return false;>    }

   check =
                    path.get(0).name.equals("A") && path.get(1).name.equals("E") &&

>            path.get(2).name.equals("F") && path.get(3).name.equals("C") &&>            path.get(4).name.equals("G"); >    if(!check)>    {

      
                    return false;

   }

>    return true;>}