The “Important Algorithms Capsule”: Part-1
In order to master Dynamic Programming, there is an ocean of algorithms and concepts that you need to dive in. Considering the same situation , I thought to come up with the “Capsule” or minimal version of most important DP algorithms that can help us solve most of the DP questions.
Let’s dive in!!
1. FLOYD WARSHALL ALGORITHM
Use case : To find the shortest path between every pair in a directed weighted graph. ( Directed-weighted graph: one point connected to other with edges that are pointed in one direction and has weight or points on the edges)
Example : Let a directed graph be in the form of a matrix where the points are connected to each other.
Points that are not connected : Represented by INF; Point where i==j i.e. same point has a value 0.
Solution : Consider the solution matrix same as the input matrix and each point k lying between every path pair (i,j)will be considered as the intermediate point, all the shortest paths are updated in the solution matrix according to this condition :
if path(i->k)+path(k->j) <path(i->j) ; where i<j
Then path(i->j)=path(i->k)+path(k->j) and point k will be included in the shortest path between two points
note : We pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
C++ implementation :
Hurrah, you made it through here !! Here’s a list of similar problems that we should solve in order to sharpen the concept :
- Find the City With the Smallest Number of Neighbors at a Threshold Distance : SOLUTION
- Cheapest Flights Within K Stops : SOLUTION
The solution to Problem 2 mentioned above might require the understanding of another tool/algorithm which we are going to discuss in Dynamic Programming : Part-2 ;)
Till then….Happy Coding :)