Dijkstra算法長度<a href="http://www.cprogramming.com/tutorial/computersciencetheory/dijkstra.html" rel="nofollow">this website's</a>僞

Question

：如果（DIST [V1] +長度（V1，V2）< DIST [V2]）：

Given a graph, G, with edges E of the form (v1, v2) and vertices V, and a 
 
source vertex, s 
 

 
dist : array of distances from the source to each vertex 
 
prev : array of pointers to preceding vertices 
 
i : loop index 
 
F : list of finished vertices 
 
U : list or heap unfinished vertices 
 

 
/* Initialization: set every distance to INFINITY until we discover a path */ 
 
for i = 0 to |V| - 1 
 
    dist[i] = INFINITY 
 
    prev[i] = NULL 
 
end 
 

 
/* The distance from the source to the source is defined to be zero */ 
 
dist[s] = 0 
 

 
/* This loop corresponds to sending out the explorers walking the paths, where 
 
* the step of picking "the vertex, v, with the shortest path to s" corresponds 
 
* to an explorer arriving at an unexplored vertex */ 
 

 
while(F is missing a vertex) 
 
    pick the vertex, v, in U with the shortest path to s 
 
    add v to F 
 
    for each edge of v, (v1, v2) 
 
     /* The next step is sometimes given the confusing name "relaxation" 
 
     if(dist[v1] + length(v1, v2) < dist[v2]) 
 
      dist[v2] = dist[v1] + length(v1, v2) 
 
      prev[v2] = v1 
 
      possibly update U, depending on implementation 
 
     end if 
 
    end for 
 
end while

是什麼意思？

特別是：長度（v1，v2）。

不應該：dist [v1] < dist [v2]夠了嗎？

Answer 1

length(v1, v2)是從節點v1到v2的邊的權重。

此條件檢查通過轉到v1然後通過邊（v1，v2）可以改進v2的路徑。