5 ms·
Efficient Graph Search: Stop when done
- SQueeeeeL 6y agoI'm really confused what problem this solves...? I think it's just supposed to stop de-queuing nodes when it's seen every node in the graph, but the time to calculate V isn't accounted for, won't some form of BFS need to be run in order to count the number of vertices in the input graph, so any time benefits will be trivial.
- kliuz 6y agoI suppose the author is assuming that the input graph is passed in a way that lets you access the number of vertices in constant time, like with a 2D array.
- mikhailfranco 6y agoThe optimization can't generalize to weighted graphs, because the first visit is not guaranteed to be the final shortest path: a path with two edges can have less weight than the first visit along one edge. But hey, it's been reviewed by Tarjan. I must be wrong.