Re: [Boost-users] [BGL] dijkstra_shortest_path fails to call initialize_vertex

From: Jens Theisen (jens-theisen-tmp01_at_[hidden])
Date: 2006-08-09 17:20:04

Hello,

By the way, isn't it rather undesirable that initialisation is done 
prior to the algorithm, rather than on-demand?

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). But you don't really want to 
build that graph, or you'll end up with quadratic complexity in any 
case, whereas you can have something like O(kn) where n is the length of 
both sequences and k is the number of "edits" in a shortest ed-script 
(if we take the priority queue lookup as constant).

There are probably other applications where it also matters. In my case, 
  the quadracticness doesn't really matters much.

Cheers,

Jens