I am trying to find the longest path in a DAG using dynamic prog. but am having

Question

I am trying to find the longest path in a DAG using dynamic prog. but am having trouble trying to understand what would be the best way to

implement a DAG using java. I am given an input file that looks like this

where the top left is the starting point and the bottom right is the final point to reach. For the first point ( 2 1) the "2" represents going right in the graph with value 2 and the "1" represents going down or essential left in the graph with value 1. The x represents that you cannot go further right/left that way. I tried to better understand the input file by creating a graph.

Would a scanner be the best way to read these points? Also, what data structure is best to represent a DAG? Could someone show me a small example in java how the graph presented above would be written?

Explanation / Answer

Generally for Graphs Adjacency List and Adjacency Matrix are the Best way to store the Graphs or define a Graph

Adjacency List

Here A,B,C,D are the nodes of a graph

where from A We can reach to B,C,D

from B we can only reach to D

from C we can only reach to D

D is the end point

this is represented as like this in Adjacency List

Adjacency Matrix

For the above Example the Adjacency Matrix would like

0 means cannot be reached , 1 means can be reached

A B C D

A -> 0 1 1 1

B-> 0 0 0 1

C-> 0 0 0 1

D-> 0 0 0 0

take the first row, row elements are from nodes and columns elements are to nodes

for example consider cell (0,2) its value is 1 , first row represenets A node and 3 rd column represents C node

it represenets A->C as A can reach to C it is set to 1.

In your use case its the weight of the graph instead of 1 , instead of 0 its x

You can use Scanner to read inputs

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.