I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too simple a solution, so I wonder if I'm missing something.

The class recently discussed dynamic programming. Is it perhaps that a different solution can get the job done faster than Dijkstra? I can come up with a dynamic programming solution that runs in O(n^3), calling on recursive solutions and taking a minimum. But that's slower than Dijkstra's. Is there a faster algorithm that I'm not seeing?

  • 2
    $\begingroup$ Yes, there is a linear time algorithm when the graph is a DAG -- which is faster than Dijkstra's algorithm. $\endgroup$ – Laakeri Mar 21 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.