**Input & Output format**

Input:

+ 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))

Output:

+ The minimum cost from vertex O to V-1

**Code**: *dijkstra.cpp*

**Complexity**: O(ElogE)

**Notes**

– After dijkstra algorithm, array *from_source[i]* = minimum cost from O to i.

– Subproblem:

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)

Code: *dijkstra-query-edge.cpp*

Happy coding

### Like this:

Like Loading...