В wiki page на Дейкстра мне сообщили, что если пункт назначения известен, я могу завершить поиск после строки 13
. Я не понимаю, как мне закончить поиск после строки 13
?Dijkstra источник в конец кратчайший путь по направленному, взвешенному графику
1 function Dijkstra(Graph, source):
2
3 dist[source] ← 0 // Distance from source to source
4 prev[source] ← undefined // Previous node in optimal path initialization
5
6 create vertex set Q
7
8 for each vertex v in Graph: // Initialization
9 if v ≠ source: // v has not yet been removed from Q (unvisited nodes)
10 dist[v] ← INFINITY // Unknown distance from source to v
11 prev[v] ← UNDEFINED // Previous node in optimal path from source
12 add v to Q // All nodes initially in Q (unvisited nodes)
13
14 while Q is not empty:
15 u ← vertex in Q with min dist[u] // Source node in the first case
16 remove u from Q
17
18 for each neighbor v of u: // where v is still in Q.
19 alt ← dist[u] + length(u, v)
20 if alt < dist[v]: // A shorter path to v has been found
21 dist[v] ← alt
22 prev[v] ← u
23
24 return dist[], prev[]
благодаря марко, не могли бы вы размещая обновления на псевдокоде здесь? – Roy
@Roy Здесь вы находитесь. –