使用鄰接矩陣（Python或僞代碼）的拓撲排序的未加權有向無環圖中的最短和最長路徑

Question

我試圖解決一個問題，我被授予作業，真的覺得自己正在顛覆算法希望這裏有人能把我推向正確的方向。

我會給予txt文件的輸入，這將是這樣的：

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 

而且我應該使用這些數據來代表圖形鄰接矩陣的箱子n個。然後我需要實現對數據3層的方法中的鄰接矩陣：

1. findLongestPath（），這將在圖中
2. findShortestPath（），這將在圖中返回的最短路徑返回最長路徑
3. totalNumberPaths（）將返回不同數量的路徑圖

我很難實現前兩個部分罰款。這是我到目前爲止有：

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 > longest_path: 
      longest_path = current_path 
     if current_path < shortest_path: 
      shortest_path = current_path 

    print "shortest: %d, longest: %d, total %d" % (shortest_path, longest_path, numPaths[numVerts-1]) 

if __name__ == "__main__": 
    main() 

顯然，當它擊中0的shortest_path更新的行0並不起作用。另外，它初始化爲0時不起作用。如果我能得到一些僞代碼，或者可能有助於使用更長或更短的方法，我相信我可以寫出相反的結果，或者我可以完全脫離基礎。

感謝您的任何意見。

編輯：

所以我想通了。這是我完成的代碼，以防有人遇到類似問題並需要幫助。

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]) 

Answer 1

想通了。這是我的最終解決方案。

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])