title: Shortest and longest path in a topologically sorted unweighted directed acyclic graph using an adjacency matrix (Python, or pseudo-code)
body: <p>I'm trying to solve a problem I was given for homework and really feel like I'm overthinking the algorithm and hoping someone here can push me in the right direction. </p>
  
  <p>I'm going to be given an input txt file which will look like this :</p>
  
  <pre><code>1    // n number of graphs
  4    // n number of vertices for graph 1
  4    // n number of edges for graph 1
  1 2  // edges given in pairs
  2 3
  2 4
  3 4 
  </code></pre>
  
  <p>And I'm supposed to use this data to crate n number of adjacency matrices representing the graphs. I then need to implement 3 methods on the data in the adjacency matrices:</p>
  
  <ol>
  <li>findLongestPath() which will return the longest path in the graph</li>
  <li>findShortestPath() which will return the shortest path in the graph</li>
  <li>totalNumberPaths() which will return distinct number of paths in graph </li>
  </ol>
  
  <p>I'm having difficulty implementing the first two parts fine. This is what I have so far:</p>
  
  <pre><code>def main():
  
  
  numGraphs = input()
  
  for x in xrange(0, numGraphs):
      numVerts = input()
      numEdges = input()
      adjMat = [[0 for x in xrange(numVerts)] for x in xrange(numVerts)] 
      for x in xrange(0, numEdges):
          edges = raw_input()
          i, padding, j = edges.rpartition(" ")
  
          i = int(i)
          j = int(j)
  
          i -= 1
          j -= 1
  
          adjMat[i][j] = 1
  
  
      numPaths = [0 for x in xrange(numVerts)]
      numPaths[0] = 1 
  
      longest_path = 1
      shortest_path = numVerts
  
      for i in xrange(0, numVerts):
          current_path = 0
          for j in xrange(0, numVerts):
              if adjMat[i][j] == 1:
                  numPaths[j] += numPaths[i]
                  current_path += 1
  
          if current_path &gt; longest_path:
              longest_path = current_path
          if current_path &lt; shortest_path:
              shortest_path = current_path
  
      print "shortest: %d, longest: %d, total %d" % (shortest_path, longest_path, numPaths[numVerts-1])
  
   if __name__ == "__main__":
       main()
  </code></pre>
  
  <p>Obviously when it hits a row of 0s the shortest_path updates to 0 and doesn't work. Plus it won't work when initialized to a 0. If I could get some pseudo code or maybe help with the longer or shorter method I'm sure I could write the opposite or maybe I'm totally off base.</p>
  
  <p>Thanks for any input.</p>
  
  <p>Edit:</p>
  
  <p>So i figured it out. Here's my finished code in case anyone has a similar problem and needs help.</p>
  
  <pre><code>numGraphs = input()
  
  for x in xrange(0, numGraphs):
      numVerts = input()
      numEdges = input()
      adjMat = [[0 for x in xrange(numVerts)] for x in xrange(numVerts)] 
      for x in xrange(0, numEdges):
          edges = raw_input()
          i, padding, j = edges.rpartition(" ")
  
          i = int(i)
          j = int(j)
  
          i -= 1
          j -= 1
  
          adjMat[i][j] = 1
  
  
      numPaths = [0 for x in xrange(numVerts)]
      numPaths[0] = 1 
  
      currentPath = [0 for x in xrange(numVerts)]
      maxPath = 1
      minPath = numVerts -1
  
      for i in xrange(0, numVerts):
          for j in xrange(1, numVerts):
              if adjMat[i][j] == 1:
                  numPaths[j] += numPaths[i]
                  currentPath[j-i] += 1
              if (currentPath[j-i] is not 0):
                  minPath = currentPath[j-i]
              maxPath = max(currentPath)
  
      print "shortest: %d, longest: %d, total %d" % (minPath, maxPath, numPaths[numVerts-1])
  </code></pre>