graph - Does Dijkstra's algorithm give shortest path always? -


i learning dijkstra's algorithm , had basic query. have graph looks follows..(non-negative nodes):

a---2-----b------16------d-----3-------f
* *
* *
3 4
* *
c----------2---------------------------e

not clear above graph display, ac has distance of 3 , ef has distance of 4.

i interested in finding shortest path between , f.

consider destination node f. when consider nearest node, d (df has weight 3 , ef 4). however, when follow path, shortest path as: a,b,d,f (total distance: 19).

a quick observation tells shortest path a,c,e,f (distance: 9). however, since in 1st step, e more distant d, followed d.

am missing here? dijkstra's algorithm not showing right result here.

yes dijkstra's gives shortest path when edge costs positive. however, can fail when there negative edge costs.


Comments

Popular posts from this blog

java - WrongTypeOfReturnValue exception thrown when unit testing using mockito -

php - Magento - Deleted Base url key -

android - How to disable Button if EditText is empty ? -