1
$\begingroup$

This question already has an answer here:

Is there a known algorithm which finds the longest path in an acyclic, directed graph like the one below?

For this example, the algorithm should calculcate a longest path of 28m graph

$\endgroup$

marked as duplicate by user91500, hardmath, Daniel W. Farlow, user137731, David K Nov 27 '16 at 15:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Casteels Dec 11 '14 at 12:22
  • $\begingroup$ Thanks to @Casteels. So the answer would be to negate the weights and apply dijkstra? $\endgroup$ – Martin Golpashin Dec 11 '14 at 12:27
  • $\begingroup$ There are a couple of problems with applying a shortest path algorithm with negative weights. Dijkstra's algorithm needs non-negative weights, and it assumes a known "source" as starting point (and finds the shortest path to a fixed target). So the proposed duplicate is a better approach. $\endgroup$ – hardmath Nov 27 '16 at 14:44
1
$\begingroup$

Hint:

  • Use dynamic programming on the partial order implied by the graph.
  • To simplfy, you can first order the graph topologically.

I hope this helps $\ddot\smile$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.