Longest acyclic path in a directed unweighted graph

by

Dynamic programming. It is also referenced in Longest path problem, given that it is a DAG.

The following code from Wikipedia:

algorithm dag-longest-path is
    input: 
         Directed acyclic graph G
    output: 
         Length of the longest path

    length_to = array with |V(G)| elements of type int with default value 0

    for each vertex v in topOrder(G) do
        for each edge (v, w) in E(G) do
            if length_to[w] <= length_to[v] + weight(G,(v,w)) then
                length_to[w] = length_to[v] + weight(G, (v,w))

    return max(length_to[v] for v in V(G))

More Related Contents:

  1. Cycles in an Undirected Graph
  2. Millions of 3D points: How to find the 10 of them closest to a given point?
  3. Graph auto-layout algorithm
  4. Find connected components in a graph [closed]
  5. Finding all the shortest paths between two nodes in unweighted undirected graph
  6. Algorithm for “nice” grid line intervals on a graph
  7. How to implement depth first search for graph with a non-recursive approach
  8. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  9. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  10. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  11. Enumerating all paths in a directed acyclic graph
  12. How does Dijkstra’s Algorithm and A-Star compare?
  13. Find cycle of shortest length in a directed graph with positive weights
  14. graph – Dijkstra for The Single-Source Longest Path
  15. Planar Graph Layouts
  16. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  17. Bridges in a connected graph
  18. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  19. Finding connected components of adjacency matrix graph
  20. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  21. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
  22. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  23. How to determine if a point is in a 2D triangle? [closed]
  24. Data structures for loaded dice?
  25. How to determine if a linked list has a cycle using only two memory locations
  26. Best word wrap algorithm? [closed]
  27. Painter puzzle – algorithmic estimation from first principles
  28. Polynomial time and exponential time
  29. The best shortest path algorithm
  30. What is the difference between Linear search and Binary search?

Leave a Comment