通信與網絡作業。。略坑啊。本來以為很簡單，但是據說又要求寫成神馬網絡傳輸的形式，平白無故增加了許多許多許多行。不過這樣以來之後自己也能看懂了。。大概能。
具體內容是路由算法中的狀態鏈路法，其實本質上對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()
