Input & Output format
+ First line: V, E (number of vertex and number of edges)
+ Following E line: U, V and C (bidirectional (U,V) edge has cost C))
+ The minimum cost from vertex O to V-1
– After dijkstra algorithm, array from_source[i] = minimum cost from O to i.
How do we know if an edge of graph belong to the minimum path or not ? Since we might have many minimum paths from O to V-1 it’s quite complicated using Dijkstra to “trace” all this path, we can just check the cost of the minimum path from O to i which contains the edge, if this value is equal to the minimum path from O to i, then we can conclude that this edge belongs to the minimum path (take a look at the code)