CODEWITHSUNDEEP
graphdirected-acyclic-graphslongest-path
blazonix
blazonix

Reputation: 433

Longest path for weighted directed acyclic graph

I'm trying to conceptualize this problem and then write Java code for it. I know there's been some discussion here, but I'm not seeing lots of answerers, so I'd like to reiterate the question by writing out my thoughts and I'm hoping to gain some feedback from you guys. Thanks!

My thoughts: For each leaf node Find the longest path from the root node to it For all paths Find the maximum path length

However, isn't this simply brute force? Are there more elegant solutions to this?

I heard of using Djikstra's algorithm with negative weights, but in some places it says that this only works on specified cases? I've also seen suggestions for the Bellman Ford algorithm, but isn't that used to find the shortest path?

Thanks!!

Upvotes: 0

Views: 4230

Answers (2)

Matthias Kricke
Matthias Kricke

Reputation: 4971

I think what you should do is to calculate all shortest paths of a root to a leaf and then take the longest of the calculated paths. In general this would be a hard problem but fortunately you are using a directed acyclic graph. In practice the algorithm will perform very well due to this restriction. The following code may help you, it was developed with yWorks and taken from this site:

// To hold an edge list for every path. 
YList allShortestPaths = new YList();

// The actual number of proper shortest paths is unknown, so we start with a really great value for 'k'. 
YCursor pathCursor = ShortestPaths.kShortestPathsCursor(graph, edgeCostsDP, startNode, endNode, Integer.MAX_VALUE);
if (pathCursor.ok())
{
  // The first path between the two nodes having least costs. 
  final EdgeList firstPath = (EdgeList)pathCursor.current();
  final double costsOfFirstPath = calculateCostsForPath(firstPath, edgeCostsDP);

  allShortestPaths.add(firstPath);
  pathCursor.next();

  // Look further. 
  while (pathCursor.ok())
  {
    EdgeList currPath = (EdgeList)pathCursor.current();
    double currCosts = calculateCostsForPath(currPath, edgeCostsDP);
    // If the current path is also a proper shortest path with costs equal to those 
    // of the first path, then add it to the list. 
    if (!(currCosts > costsOfFirstPath))
    {
      allShortestPaths.add(currPath);
      pathCursor.next();
    }
    else
      break;
  }
}

Upvotes: 3

nilmish
nilmish

Reputation: 21

We can do topological sort to get an ordering of the vertices of the directed acyclic graph(DAG). Once we have the topological ordering we can apply dynamic programming to get the longest path in the DAG.

Let the indices of the vertices after toposort be 0,1,2,....,n-1 (total n vertices in the graph)

Let F[i] be the value of the longest path that end at vertex i.

Then for each outgoing edge from i to all j we can update F[j] as F[j]=max(F[j],F[i]+1)

We can start by initialising all F[i]'s to zero Then loop from i=1 to n-1

Final answer would be max{F[i]} 0<=i<=n-1

Upvotes: 2

Related Questions