Physical explanation of Dijkstra's algorithm (2011) [video]
1–3 of 3 posts
Re: Physical explanation of Dijkstra's algorithm (2011) [video]
#2The 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 AEdit: But it seems like for undirected graphs, the edge weights are always positive and by definition symmetric which is sufficient that string-dijkstra works.
Re: Physical explanation of Dijkstra's algorithm (2011) [video]
#3The 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 Edit: But it seems like for undirected graphs, the edge wei…
Textbook Dijkstra doesn't work with negative edges. See for example
http://stackoverflow.com/questions/6799172/negative-weights-...