Directed Acyclic Graph (DAG)

Revision en1, by LastTry, 2016-04-20 16:04:22

Hey, guys!

I've been working on a problem recently but I need some help with the idea of it. Here it is:

You are given a directed acyclic graph with the length of the edges between two vertices. What you have to do is find the longest path in the graph, starting from the beginning vertex (it's 1). The input contains on the first line the number of vertices (N) and number of edges (M). Then it is followed by M lines, each of whom contains 3 numbers — the first 2 are the indexes of the two vertices which are connected and the 3rd number is the length of the edge between them. The output should contain the longest path in the DAG.

Example input:

5 8 1 2 5 1 4 4 1 5 1 2 3 3 2 5 1 4 3 2 5 3 3 5 4 2

Example output:

10

Explanation: Here's the path in this case: 1 2 5 4 3

Tags graphs, graph, dag

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LastTry 2016-04-20 16:04:22 838 Initial revision (published)