Returning only the peaks in the shortest path

Question

I know the name is a little messy, but I don’t know how to better explain it.

What am I trying to do:

Using the graph found in the text file, find and print the shortest path (minimum number of vertices) from vertex A to vertex B.

Note: use the width search, not Dijkstra's.

What I have:

A working algorithm that applies BFS on a chart but does not have a good way to actually print the shortest path.

I find it difficult to distinguish a vertex in the shortest path from one that is simply executed through the algorithm, but not in the shortest path.

For example: find the shortest path between 0 and 4. 0 connects to 1.2 and 3. 1 connects to 4. My path turns out to be [0,1,2,3,4] instead of [0,1,4].

I was not able to find threads asking the same question, or any BFS passes that include this, so I'm not sure if I am doing this much more complicated than that?

Edit: code for those who might be interested (not sure if I avoid circles?)

Edit 2: Changed the way my stack path is stored.

public String findPath(int v, int w) { Queue<Integer> q = new LinkedList<Integer>(); boolean[] visited = new boolean[g.numVertices()]; q.add(v); Stack<Integer> path = new Stack<Integer>(); while(q.peek() != null) { runBFS(q.poll(),w,visited,q,path); } return path.toString(); } private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) { if(visited[v]) { } else if(v == w) { path.add(v); q.clear(); } else { path.add(v); visited[v] = true; VertexIterator vi = g.adjacentVertices(v); while(vi.hasNext()) { q.add(vi.next()); } } } 

Some explanation of variables and methods:

v = vertex of origin

w = target vertex

g = graph

vi = normal iterator that iterates over neighbors v

Thank you for reading!

Answer 1

You will need to have a specific path field for each vertex. This way you can track the paths you have chosen, hence the shortcut found. I will use the String array, just as you used the Boolean array to store the visited vertices.

 public String findPath(int v, int w) { Queue<Integer> q = new LinkedList<Integer>(); boolean[] visited = new boolean[g.numVertices()]; String[] pathTo = new String[g.numVertices()]; q.add(v); pathTo[v] = v+" "; while(q.peek() != null) { if(runBFS(q.poll(),w,visited,q,pathTo)) break; } return pathTo[w]; } private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) { if(visited[v]) { } else if(v == w) return true; } else { visited[v] = true; VertexIterator vi = g.adjacentVertices(v); while(vi.hasNext()) { int nextVertex = vi.next(); pathTo[nextVertex] = pathTo[v] + nextVertex + " "; q.add(nextVertex); } } return false; } 

Answer 2

Another compact (spatial) solution proposed by our assistants and not using the O (n ^ 2) storage space should contain every node store from which the node came from. This can be done by changing the list of visits to an integer array ( int[] visited ).

step 1: initialize the visited list so that each element is '-1' or "unvisited"

step 2: mark the first node as visited itself visited[v] = v;

Make BFS (like you, with the following changes :)

when moving from v → v_next:

 if(visited[v_next] == -1) { visited[v_next] = v; q.put(v_next); } // else skip it, it already been visited 

Thus, if w is available, the visitor [w] will save which node it came from, from this node, you can go back to v and finally print them in reverse order. (This is done either using the stack or using the recursive method.)

Hope this makes sense. :)

Answer 3

When you store a vertex in the BFS queue, you also need to save a copy of the path that it was reached so that it is accessible after that vertex is deleted. As now, your code does not store any information about the path in the queue with the queue - it only stores the list of nodes that it visits.

You can, for example, use a separate queue that will be processed in parallel, in which you will store the current path, and then restore it as soon as you delete the next vertex for the search.

Answer 4

You need to push the current node to the stack and print the entire stack only after reaching the goal.