Difference between branch & bound (+ extended list) and Dijkstra's Algorithm on Graphs

Question

I was working through http://youtu.be/gGQ-vAmdAOI?t=23m14s when at 23:14 I felt that branch & bound with an "extended list" was very similar to Dijkstra's algorithm. Later on in the lecture when the algorithm is again extended with an admissable heuristic, we get A*.

That led me into thinking that Dijkstra's algorithm is this very subclass of branch & bound. Is that right?

---

To summarize the lecture:

Search algorithms are explored. In particular, they start from a simple branch & bound solution:

Until the destination node is visited (extended), visit the node with the shortest distance from the source and add its successors to the priority queue of nodes to visit (sorted by min distance). This doesn't yet detect cycles (e.g. visits nodes more than once) and is rather inefficient because of combinatorial explosion.

A simple extension causes the algorithm to perform much better: Remembering which nodes were already visited (extended, hence extension list). No node is visited twice now and the algorithm performs considerably better.

In the last part, an admissable heuristic is added to the mix to get A*.

I hope this is enough information and that I don't have to copy the examples from the lecture. If it isn't, let me know and I'll do though!

Answer 1

The difference is only in implementation, the idea is the same. What makes Dijkstra's algorithm special is that it's branch & bound done with a heap (which gives you a big speedup).

Answer 2

Yes you are right, as long as we assume that the extended list can be dynamically checked. If we have a state in the "extended list" ,that means we have visited that state with a path with value = n.

While we run the algorithm if we come across a path that visits that node with value < n, the "extended list" gives us the option to replace that path on the priority queue of the BnB, which is essentially Djikstra. You can implement that with a hash table that keeps for each node the value of the shortest path for every moment the algorithm runs just like Djikstra.