I am having trouble with my coding. can someone help me with the public List<int

Question

I am having trouble with my coding. can someone help me with the public List<integer> method about the shortest path for my graph class. here is my full code for a better understanding:

public class Graph
{
    private boolean[][] adjacency;

    // this graph has vertices labeled 0 to numVertices-1
    public Graph(int numVertices)
    {
        adjacency = new boolean[numVertices][numVertices];
        for(boolean[] row: adjacency)
            Arrays.fill(row, Boolean.FALSE);
    }

    // store a directed edge from fromVertex to toVertex
    public void setEdge(int fromVertex, int toVertex)
    {
        adjacency[fromVertex][toVertex] = true;
    }

    // return a list of connected vertices to get from source to destination
    // return null if path does not exist
    public List<Integer> shortestPath(int source, int destination)
    {
        // build up bookkeeping according to unweighted single source shortest
        // path algorithm in book
        // recover path from source to destination using your bookkeeping
    }
}

any help will be appreciated and it has to go with this tester class below:

public class GraphTester
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);

        // read numVertices and numEdges from scanner
        int numVertices = input.nextInt();
        int numEdges = input.nextInt();

        // create a new Graph with numVertices vertices
        Graph graph = new Graph(numVertices);

        // read numEdges pairs of source, destination vertices and store in
        // graph data structure
        for (int i=0; i<numEdges; i++)
        {
            int s = input.nextInt();
            int d = input.nextInt();
            graph.setEdge(s,d);
        }

        // print shortest path to all vertices from vertex 0
        for (int i=0; i<numVertices; i++)
        {
            System.out.print("Path to vertex " + i + ": ");
            List<Integer> path = graph.shortestPath(0, i);
            if (path == null)
            {
                System.out.println("No path");
            }

            else
            {
                System.out.println(path);
            }
        }

    }
}

I really need help with that method in the graph class so I can get this program to work!! anybody that can save me from this problem that I am stuck on will really help

Explanation / Answer

Complete Program:

// File: Edge.java
public class Edge
{
public final int vert1, vert2;
public final int dist;

public Edge(int vert1, int vert2, int dist)
{
  this.vert1 = vert1;
  this.vert2 = vert2;
  this.dist = dist;
}
}

// File: Vertex.java
import java.util.*;
public class Vertex implements Comparable<Vertex>
{
public final int value;
public int dist = Integer.MAX_VALUE;
public Vertex prev = null;
public final Map<Vertex, Integer> neighbours = new HashMap<>();

public Vertex(int value)
{
  this.value = value;
}

public void printPath()
{
  if(this == this.prev)
  {
   System.out.printf("%d", this.value);
  }
  else if(this.prev == null)
  {
   System.out.printf("%d(null)", this.value);
  }
  else
  {
   this.prev.printPath();
   System.out.printf(" -> %d", this.value);
  }
}

public int compareTo(Vertex other)
{
  return Integer.compare(dist, other.dist);
}
}

// File: Graph.java
import java.util.*;
class Graph
{
private final Map<Integer, Vertex> graph;

public Graph(Edge[] edges)
{
  graph = new HashMap<>(edges.length);
  
  for(Edge edg : edges)
  {
   if(!graph.containsKey(edg.vert1))
    graph.put(edg.vert1, new Vertex(edg.vert1));
   
   if(!graph.containsKey(edg.vert2))
    graph.put(edg.vert2, new Vertex(edg.vert2));
  }
  
  for(Edge edg : edges)
  {
   graph.get(edg.vert1).neighbours.put(graph.get(edg.vert2), edg.dist);
  }
}

public void findShortestPath(int startValue)
{
  if(!graph.containsKey(startValue))
  {
   System.err.printf(startValue + " is not found");
   return;
  }
  
  final Vertex source = graph.get(startValue);
  NavigableSet<Vertex> ns = new TreeSet<>();
  
  for(Vertex vert : graph.values())
  {
   vert.prev = vert == source ? source : null;
   vert.dist = vert == source ? 0 : Integer.MAX_VALUE;
   ns.add(vert);
  }
  findShortestPath(ns);
}

private void findShortestPath(final NavigableSet<Vertex> ns)
{
  Vertex v1, v2;
  while(!ns.isEmpty())
  {
   v1 = ns.pollFirst();
   if(v1.dist == Integer.MAX_VALUE)
    break;
   
   for(Map.Entry<Vertex, Integer> a : v1.neighbours.entrySet())
   {
    v2 = a.getKey();
    final int alternateDist = v1.dist + a.getValue();
    if(alternateDist < v2.dist)
    {
     ns.remove(v2);
     v2.dist = alternateDist;
     v2.prev = v1;
     ns.add(v2);
    }
   }
  }
}

public void printPath(int endValue)
{
  if(!graph.containsKey(endValue))
  {
   System.err.printf(endValue + " is not found");
   return;
  }
  
  graph.get(endValue).printPath();
  System.out.println();
}

public void printAllPaths()
{
  for(Vertex v : graph.values())
  {
   v.printPath();
   System.out.println();
  }
}
}

// File: GraphTester.java
public class GraphTester
{
private static final Edge[] GRAPH = {new Edge(1, 2, 7),
   new Edge(1, 3, 9), new Edge(1, 6, 14),
   new Edge(2, 3, 10), new Edge(2, 4, 15),
   new Edge(3, 4, 11), new Edge(3, 6, 2),
   new Edge(4, 5, 6), new Edge(5, 6, 9),};

public static void main(String[] args)
{
  Graph g = new Graph(GRAPH);
  
  int start = 1;
  
  for(int end = 2; end <= 6; end++)
  {
   g.findShortestPath(start);
   g.printPath(end);
  }
}
}

Sample Output:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.