0
из this website's псевдокоде:длина Алгоритм Дейкстры
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] + длина (v1, v2) < расстояние [v2])?
в частности: длина (v1, v2).
не должно: dist [v1] < dist [v2] достаточно?
Инвариант состоит в том, что 'dist [i]' содержит наименьшее расстояние 'i' от источника. поэтому всякий раз, когда вы устанавливаете 'dist [j]' из 'i', вас интересует, как далеко находится' j' от источника, и это 'dist [i] + length (i, j)' – mangusta
'dist [i ]
mangusta