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（）