I know the title is a bit messy, but I don't know how to explain it better.
What I'm trying to do:
Using a graph found in a text file, find and print the shortest path (minimum amount of vertices) from vertex A to vertex B.
Note: using breadth-first search, not Dijkstra's.
What I've got:
A working algorithm that applies BFS on the graph, but no good way of actually printing out the shortest path.
I'm having a hard time distinguishing a vertex in the shortest path from one that is simply run 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 haven't been able to find any threads asking the same question, or any walk-through of BFS that includes this, so I'm not sure if I'm making this out to be way harder than it is?
Edit: code for those who may be interested (not sure at all if I'm avoiding circles?)
Edit 2: Changed the way I store my path to a Stack.
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 = a normal iterator that iterates over the neighbours of v
Thanks for reading!
You will have to have specific path field for each vertex. That way you can keep track of the paths you've chosen, hence the short path found. I will use an String array, just like you used the Boolean array for storing 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;
}