Dijsktra的最短路徑算法

Question

當我運行此，最終輸出與列的表格：

Vertex - DisVal - PrevVal - Known. 

連接到我的開始節點的兩個節點顯示正確的值，但沒有其他人最終得到更新。如果有人想看，我可以包含完整的程序代碼，但我知道這裏的問題是孤立的。我認爲這可能與不以正確的方式改變索引有關。這是一個簡單的dijsktra的btw，而不是堆/ Q版本。

這裏的代碼的其餘部分：http://ideone.com/UUOUn8

的adjList看起來像這樣：[1：2，4，2：6,3，...]，其中它顯示了連接到一個頂點的每個節點。 DV =距離值（權重），PV =先前的值（節點），稱爲=已它蜂訪問

def dijkstras(graph, adjList): 
    pv = [None] * len(graph.nodes) 
    dv = [999]*len(graph.nodes) 
    known = [False] * len(graph.nodes) 

    smallestV = 9999 
    index = 0 
    dv[0] = 0 
    known[0] = True 
    for i in xrange(len(dv)): 
     if dv[i] < smallestV and known[i]: 
      smallestV = dv[i] 
      index = i 
     known[index] = True 
     print smallestV 
     print index 
     for edge in adjList[index]: 
      if (dv[index]+graph.weights[(index, edge)] < dv[edge]): 
       dv[edge] = dv[index] + graph.weights[(index, edge)] 
       pv[edge] = index 

    printTable(dv, pv, known) 

Answer 1

第一次迭代設置smallestV和索引爲0無條件，並且它們不會改變之後（假定非負權重）。

很難說出你在這裏要做什麼。