I am trying to implement a shortest path algorithm using BFS. That is I am trying to find the shortest path from a specified vertex to every other vertex. However, its a special case where all edge weights are either 1 or 2.
I know it could be done with Dijkstra's algorithm but I must use Breadth First Search.
So far I have a working version of BFS that searches first for a vertex connected with an edge of weight 1. If it cannot find it, then returns a vertex connected with an edge of weight 2. After thinking about it, this is not the correct way to find the shortest path.
The problem is I cannot think of any reasoning why BFS would work with weights 1 or 2, as opposed to any weight.
Here is the code:
public void addEdge(int start, int end, int weight)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
edge_weight[start][end] = weight;
edge_weight[end][start] = weight;
}
// -------------------------------------------------------------
public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2;
while( !theQueue.isEmpty() ) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while( (v2=getAdjUnvisitedVertex(v1)) != -1 ){// get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.insert(v2); // insert it
}
} // end while(queue not empty)
// queue is empty, so we're done
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()
// -------------------------------------------------------------
// returns an unvisited vertex adj to v -- ****WITH WEIGHT 1****
public int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++)
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false && edge_weight[v][j] == 1){
//System.out.println("Vertex found with 1:"+ vertexList[j].label);
return j;
}
for (int k = 0; k < nVerts; k++)
if (adjMat[v][k] == 1 && vertexList[k].wasVisited == false && edge_weight[v][k] == 2){
//System.out.println("Vertex found with 2:"+vertexList[k].label);
return k;
}
return -1;
} // end getAdjUnvisitedVertex()
// -------------------------------------------------------------
}
////////////////////////////////////////////////////////////////
public class BFS{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for bfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addEdge(0, 1,2); // AB
theGraph.addEdge(1, 2,1); // BC
theGraph.addEdge(2, 0,1); // AD
System.out.print("Visits: ");
theGraph.bfs(); // breadth-first search
System.out.println();
} // end main()
}
The problem then is, that I don't know why BFS can work for the shortest path problem with edges of weight 1 or 2 as opposed to any edges of any weight.
Any help is appreciated.
Thanks!
