title: Intuition behind the algorithm to compute single source shortest path for every vertex in DAG
body: <p>The algorithm is as follows:</p>
  
  <blockquote>
    <p>The algorithm starts by topologically sorting the dag (see Section 22.4) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.</p>
  </blockquote>
  
  <p>Can somebody tell me the intuition behind it? And using that intuition please tell how do we find longest path just be negating the edge weights and running the algorithm</p>
  
  <p>We cannot use Dijkstra's algorithm as edges are allowed to have negative weights.</p>