function Dijkstra(Graph, source):
for each vertex v in Graph: // Initializations
dist[v] := infinity ; // Unknown distance function from source to v
previous[v] := undefined ; // Previous node in optimal path from source
end for ;
dist[source] := 0 ; // Distance from source to source
Q := the set of all nodes in Graph ;
// All nodes in the graph are unoptimized - thus are in Q
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[] ;
if dist[u] = infinity:
break ; // all remaining vertices are inaccessible from source
fi ;
remove u from Q ;
for each neighbor v of u: // where v has not yet been removed from Q.
alt := dist[u] + dist_between(u, v) ;
if alt < dist[v]: // Relax (u,v,a)
dist[v] := alt ;
previous[v] := u ;
fi ;
end for ;
end while ;
return dist[] ;
end Dijkstra.
приведенный выше алгоритм упоминается в Википедии для кратчайшего пути Дейкстры. Здесь я не могу понять, что, хотя мы установили расстояния до всех вершин как бесконечность [строка номер 3], в строке 9 мы назначаем u := vertex in Q with smallest dist[]
, но поскольку все расстояния бесконечны (как указано в строке 3) как может быть минимальное расстояние?Вопрос о реализации алгоритма Дейкстры в Википедии
получил это, думал, что dist_between (u, v) также вычисляет расстояния на основе dist [] –