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

php - Magento - Deleted Base url key -

javascript - Tooltipster plugin not firing jquery function when button or any click even occur -

java - WrongTypeOfReturnValue exception thrown when unit testing using mockito -