Getting a Graph's shortest path between two vertices using BFS
>> Thursday, June 9, 2011
Long title indeed, but this is a rather specific entry. I've been working with graphs lately, for university, and I'm afraid there are lots and lots of different properties and algorithms (you can imagine studying that for an exam is a pain in the ass) but well, I tried searching for this on Google with no luck, there are many algorithms for getting the shortest path between two vertex, and many sites say "It can be done using BFS" but they do not explain how.
So, I found a rather nice and easy solution. First of all, let's say G is a simple graph, with no directed edges, and we don't consider edges' weight. I'll use pseudo-code in this entry since it's more CS oriented.
First of all, if you don't know what BFS is, it's Breadth First Search, it's a way of iterate through a graph, in which you go by levels.
 |
| BFS Animation |
You can see wikipedia for more info, I'll assume you know the algorithm, at least just on paper, the algorithm is like this:
Input: a vertex called start Let Q be a queue Q.enqueue(start) visit start while(Q is not empty) w = Q.dequeue() for each adyacent vertex v of w do if v is not visited mark v as visited add v to queue visit v
That's it. Basically, when you solve a problem using an algorithm like this, what you want to work on is on the "visit v" part, what we are gonna do is use a map, in which we will save each vertex we visit, and once we reached our end vertex, we simply "go back". A map is a data structure which has a Key and a Value, so we will use the Key as our vertex, and the value will be the vertex' parent, that way we can just go back and return a list of visited vertex' which make the shortest path from START to END.
Input: a vertex called start, and a vertex called end
Output: a list containing the shortest path from start to end, or null if it cannot find a path Let Q be a queue
Let M be a map Q.enqueue(start) map.put(start, null) // Start has no parent! while(Q is not empty) w = Q.dequeue() for each adyacent vertex v of w do if v is not visited mark v as visited add v to queue if(v == end)
Let L be a listwhile(v != null)L.addFirst(ww)ww = M.get(ww)return Lreturn null
There it is, hopefully someone will find it useful! Note that basically the only part that changes is the 'visit' part.
I'll leave the Java code just for the sake of it ;) Sorry it's in spanish, as it's from university, but this should not be much problem. Read more...
