What happens when the graph is not Directed Acyclic Graphs (DAG)?
If the graph contains a cycle, then some states would lead back to themselves after a series of transitions. This would lead to infinite calculations. Thus, answer will not exist if the graph is cyclic in this case. As shown in below image, we potentially keep traversing the cycle indefinitely, making it impossible to find the longest path.
DP on Directed Graphs
Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)
Pre-Requisite:
What is Directed Graph? | Directed Graph meaning
Dynamic Programming (DP) Tutorial with Problems
Every Dynamic Programming problem can be represented as a Directed Acyclic Graph(DAG). The nodes of the DAG represent the subproblems and the edges represents the transitions between the subproblems.
Table of Content
- Relationship Between Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)
- What happens when the graph is not DAG?
- How to Solve Dynamic Programming (DP) Problems on Directed Graphs
- Practice Problems on Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)
Contact Us