Python實現通信網絡的dijkstra算法

通信與網絡作業。。略坑啊。本來以為很簡單，但是據說又要求寫成神馬網絡傳輸的形式，平白無故增加了許多許多許多行。不過這樣以來之後自己也能看懂了。。大概能。

具體內容是路由算法中的狀態鏈路法，其實本質上對Dijkstra算法一點改進都沒有。。貼代碼留存。python版。目測是對的，如果是錯的請告訴我。

# coding=utf-8
 # 模擬網絡通信路由表建立的Daoijkstra算法實現
 # Author bnkR.
 import random
 def d_gen(d_max, thr, INF):
     # 此函數用來生成一條隨機長度的邊，thr是無窮大的阈值
     d = random.randint(1, d_max)
     if d < thr:
         return d
     else:
         return INF
 
 # 通過LSP表返回鄰居
 def neighbor(lsp, INF):
     return [ix for ix in range(len(lsp)) if lsp[ix] != INF and lsp[ix] != 0]
 
 # Dijkstra算法
 def dijkstra(gram, vs, INF):
     vNum = len(gram[0])
     cfmTable = [vs] #證實表
     cfmInfo = [(INF, INF) for ix in range(vNum)] #證實表信息(距離,下一跳)
     cfmInfo[vs] = (0, vs)
     testTable = neighbor(gram[vs], INF) #試探表
     testInfo= [(gram[vs][ix], ix) for ix in range(vNum)] #試探表信息(距離,下一跳)
     v_next = vs
     while True:
         lsp = gram[v_next]
         #獲取v_next的LSP包，現實中可以調用其他函數
         for v in neighbor(lsp, INF):
             #遍歷v_next的所有鄰居
             if v not in cfmTable and v not in testTable:
                 #如果此鄰居不在證實表和試探表中，則加入試探表
                 testTable.append(v)
             if lsp[v] + cfmInfo[v_next][0] < testInfo[v][0]:
                 #如果在試探表中，則比較它到源的距離是否比試探表中之前存的更小，是則替換
                 testInfo[v] = (lsp[v] + cfmInfo[v_next][0], cfmInfo[v_next][1])
         if not len(testTable):    #檢查試探表是否非空
             break
         #找到試探表中的最小節點，將其加入證實表，並指定為下一個v_next
         minCostNode = testInfo[testTable[0]]
         vmin = testTable[0]
         for v in testTable:
             if testInfo[v][0] < minCostNode[0]:
                 minCostNode = testInfo[v]
                 vmin = v
         cfmTable.append(vmin)
         cfmInfo[vmin] = minCostNode
         v_next = vmin
         testTable = [v for v in testTable if v != v_next]
     return (cfmTable, cfmInfo)
 
 # 主函數，圖的生成，通過調整阈值來隨機確定一些無法達到的邊。
 def main():
     INF = 1000
     vNum = 10
     gram = [[d_gen(100, 10, INF) for col in range(vNum)] for row in range(vNum)]
     # 對稱化矩陣
     for row in range(vNum):
         gram[row][row] = 0
         for col in range(row):
             gram[row][col] = gram[col][row]
     for row in range(vNum):
         print gram[row]
     print dijkstra(gram, 0, INF)
    
 if __name__ == "__main__":
     main()