reset password
Author Message
skim144
Posts: 63
Posted 13:36 Nov 12, 2014 |

I have a question:

 

In the second video, 'Dijkstra's Algorithm: example' at 11:30,

Why does Dijkstra's Algorithm return s -> t, instead of s-> v -> t? 

Doesn't s-> v -> t have score of -4 which is less than score of s -> t, which is -2?

 

hal255
Posts: 51
Posted 21:55 Nov 12, 2014 |

My guess is he was demonstrating why Dijkstra's algorithm doesn't always work properly. 

It will compare (s -> t) vs (s -> v) first and asks "which is shorter?"

s -> v has path = 1

s -> t has path = -2

since t is the endpoint and is found, then A[t] is -2.