Which part were you having trouble understanding? I'll be happy to clarify or help. Remember, Dijkstra's algorithm classically produces a shortest path tree from the start/source vertex. Keep in mind, in this counterexample, I show how the presumed shortest path tree [it isn't actually] that would be produced by Dijkstra's algorithm does not contain all the shortest paths. Simple path s-u-v is the shortest simple path from s to v (length is -1), but s-v-u is the shortest simple path from s to u (length is 0). Dijkstra's algorithm will just give s-u-v as the presumed "shortest path tree" [which will contain an incorrect shortest simple path, namely the one for s to u]. In other words, as I explained in the video, this instance has no shortest path tree!
If you look at the example, Dijkstra's algorithm is a greedy algorithm, so where it is currently at will always choose the minimum weight option. Starting from vertex S, you either go to U (cost of S->U is C) or go to V (cost of S->V is C + 1) C is less than C + 1 so the algorithm will go from S -> U costing C. This would mark S and U as visited and any other edges to U would not be considered in the future. So the only option is S -> V which cost C + 1. V -> U is not considered because we've already marked U from the previous traversal. Even though V -> U cost -(C+1). Thats how I understand the example, hoped it helps!
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
Thank You Sir ❤
Anytime, have a beautiful day! :)
Not clear
Which part were you having trouble understanding? I'll be happy to clarify or help.
Remember, Dijkstra's algorithm classically produces a shortest path tree from the start/source vertex. Keep in mind, in this counterexample, I show how the presumed shortest path tree [it isn't actually] that would be produced by Dijkstra's algorithm does not contain all the shortest paths. Simple path s-u-v is the shortest simple path from s to v (length is -1), but s-v-u is the shortest simple path from s to u (length is 0). Dijkstra's algorithm will just give s-u-v as the presumed "shortest path tree" [which will contain an incorrect shortest simple path, namely the one for s to u].
In other words, as I explained in the video, this instance has no shortest path tree!
If you look at the example, Dijkstra's algorithm is a greedy algorithm, so where it is currently at will always choose the minimum weight option.
Starting from vertex S, you either go to U (cost of S->U is C) or go to V (cost of S->V is C + 1)
C is less than C + 1 so the algorithm will go from S -> U costing C.
This would mark S and U as visited and any other edges to U would not be considered in the future.
So the only option is S -> V which cost C + 1.
V -> U is not considered because we've already marked U from the previous traversal.
Even though V -> U cost -(C+1).
Thats how I understand the example, hoped it helps!