Hello, after the discussion about on-demand vertex initialisation I implemented a diffing algorithm on top of BGL's dijkstra. I thought the main problem is that BGL is inherently linear in the number of vertices (because it initialises some maps on each vertex prior to running the algo), but in practice, for diffing files, that's probably not too relevant, as the case of two files being pretty different is not a rare one (and two completely different files will need to access any node). The algorithm used by gnu diff is, though also quadratic in the input, linear in space usage, which one can't say for the dijsktra approach. (I haven't look at the algorithm, but they cite a paper which suggests that.) And gnu diff is much faster than my program in practice, though my one is probably fast enough for what I want to use it for. Jens