Doug Gregor wrote:
I once had the idea of using boost::graph to implement a diffing algorithm by applying dikstra to the edit graph of two sequences (that's the popular way of doing this I think).
I didn't know that. Very interesting!
Well, sorry, I meant viewing it as finding the shortest path in the edit graph is popular. Rooting in on dijkstra itself probably isn't.
There is a "no_init" version of Dijkstra's algorithm that skips the initialization entirely. Of course, the user would be responsible for initializing property map values for vertices on demand, e.g., in examine_edge. I've seen the no_init form of Dijkstra's used for other "implicit" graphs, which have similar properties to the one you describe.
That doesn't help very much because even that is initialising it's relaxed_heap with num_vertices(g), so the algorithm will linear in the number of it's vertices anyway. You really want to drop the VertexListGraph requirement for the no_init version (or yet another one). Jens