Python实现通信网络的dijkstra算法

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