Python Dijkstra算法

Question

我正在嘗試寫Dijkstra的算法，但是我正在努力如何在代碼中「說」某些事情。 爲了形象化，這裏有我想要使用數組所代表的列：

max_nodes 
    A B C   Length  Predecessor  Visited/Unvisited 
A 0 1 2    -1            U 
B 1 0 1    -1            U 
C 2 1 0    -1            U 

所以，會有好幾個陣列，在下面我的代碼所示：

def dijkstra (graph, start, end) 

network[max_nodes][max_nodes] 
state [max_nodes][length] 
state2 [max_nodes][predecessor] 
state3 [max_nodes][visited] 
initialNode = 0 

    for nodes in graph: 
     D[max_nodes][length] = -1 
     P[max_nodes][predecessor] = "" 
     V[max_nodes][visited] = false 

     for l in graph: 

     length = lengthFromSource[node] + graph[node][l] 
      if length < lengthFromSourceNode[w]: 
      state[l][length] = x 
      state2[l][predecessor] 
      state3[l][visited] = true 
      x +=1 

粗體部分是我我試圖實現算法的這一部分：

3.對於當前節點，考慮它的所有未訪問的鄰居並計算它們的暫定距離。例如，如果當前節點（A）的距離爲6，並且與另一個節點（B）連接的邊的長度爲2，則通過A到B的距離爲6 + 2 = 8。如果此距離小於先前記錄的距離，則覆蓋距離
4.當我們完成考慮當前節點的所有鄰居時，將其標記爲已訪問。被訪問的節點將不會再次被檢查;它記錄的距離現在是最終的和最小的

我想我是在正確的軌道上，我只是被困在如何說'在一個節點開始，從源節點獲取長度，如果長度較小，覆蓋以前的值，然後移動到下一個節點

Answer 1

首先，我認爲這是一個家庭作業問題，因爲最好的建議是不打擾自己寫，而是在網上找到現有的實現。 Here's one that looks pretty good, for example。

假設你做需要重新發明輪子，那裏引用的代碼使用字典來存儲節點數據。所以你餵它像這樣：

{ 
    's': {'u' : 10, 'x' : 5}, 
    'u': {'v' : 1, 'x' : 2}, 
    'v': {'y' : 4}, 
    'x': {'u' : 3, 'v' : 9, 'y' : 2}, 
    'y': {'s' : 7, 'v' : 6} 
} 

這似乎是一個更直觀的方式呈現您的圖形信息。訪問過的節點和距離也可以保存在字典中。

Answer 2

我還用字典存儲網絡。

創建網絡字典（用戶提供）

net = {'0':{'1':100, '2':300}, 
     '1':{'3':500, '4':500, '5':100}, 
     '2':{'4':100, '5':100}, 
     '3':{'5':20}, 
     '4':{'5':20}, 
     '5':{} 
     } 

最短路徑算法（用戶需要指定開始和終端節點）

def dijkstra(net, s, t): 
    # sanity check 
    if s == t: 
     return "The start and terminal nodes are the same. Minimum distance is 0." 
    if net.has_key(s)==False: 
     return "There is no start node called " + str(s) + "." 
    if net.has_key(t)==False: 
     return "There is no terminal node called " + str(t) + "." 
    # create a labels dictionary 
    labels={} 
    # record whether a label was updated 
    order={} 
    # populate an initial labels dictionary 
    for i in net.keys(): 
     if i == s: labels[i] = 0 # shortest distance form s to s is 0 
     else: labels[i] = float("inf") # initial labels are infinity 
    from copy import copy 
    drop1 = copy(labels) # used for looping 
    ## begin algorithm 
    while len(drop1) > 0: 
     # find the key with the lowest label 
     minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label 
     # update labels for nodes that are connected to minNode 
     for i in net[minNode]: 
      if labels[i] > (labels[minNode] + net[minNode][i]): 
       labels[i] = labels[minNode] + net[minNode][i] 
       drop1[i] = labels[minNode] + net[minNode][i] 
       order[i] = minNode 
     del drop1[minNode] # once a node has been visited, it's excluded from drop1 
    ## end algorithm 
    # print shortest path 
    temp = copy(t) 
    rpath = [] 
    path = [] 
    while 1: 
     rpath.append(temp) 
     if order.has_key(temp): temp = order[temp] 
     else: return "There is no path from " + str(s) + " to " + str(t) + "." 
     if temp == s: 
      rpath.append(temp) 
      break 
    for j in range(len(rpath)-1,-1,-1): 
     path.append(rpath[j]) 
    return "The shortest path from " + s + " to " + t + " is " + str(path) + ". Minimum distance is " + str(labels[t]) + "." 

# Given a large random network find the shortest path from '0' to '5' 
print dijkstra(net=randNet(), s='0', t='5')