Dijkstra & some properties

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s