[maweki]

The unanswered question is, whether this always works with any metric that works with Dijkstra.

And the answer, I guess, is no. Dijkstra works with negative edge weights (although no negative loops). This doesn't translate to string. Also there are some other restrictions like that any edge is always symmetric where with Dijkstra it needn't be. A>B (3) and A<B (5) would be the lower for both with regards of the physics.

Edit: But it seems like for undirected graphs, the edge weights are always positive and by definition symmetric which is sufficient that string-dijkstra works.

[adrianN]

Textbook Dijkstra doesn't work with negative edges. See for example

http://stackoverflow.com/questions/6799172/negative-weights-...