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!
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).