title: Shortest path in an edge-weighted DAG with multiple source vertices?
body: <p>Given an algorithm A that computes the longest path from a source vertex s in a DAG G with non-negative edge weights. What is the minimum number of times required to run the algorithm A to find the longest path in a DAG G?</p>
  
  <p>One way is to figure out the multiple source vertices, this can be achieved in O(|Edges|). And then run Algorithm A with each of these vertices as a source vertex. This will require running algorithm A NumberOfSourceVertices times.</p>
  
  <p>Can we do better ?</p>