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. |