2015-08-26 2 views
1

В 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[] 

ответ

1

Википедия является неправильной, правая линия в этом алгоритме 16. Редактирование, вероятно, испортило номера строк или абзац ниже них.

Что означал этот абзац, так это то, что если вас интересует только кратчайший путь от вершины S до Q, вы можете спокойно выйти из цикла, когда Q найден, поскольку любой другой путь будет иметь более высокую стоимость, чтобы достичь его , ПСЕВДОКОД следует

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   
(extra) if u == destination_point then break loop 

Когда вы сталкиваетесь с конечной точкой Q, вы можете спокойно пропустить часть обновления, где вы обновляете любую соседнюю вершину с кратчайшим путем его достижения -> вы уже нашли место назначения. Чтобы восстановить путь, просто переверните вектор prev от destination_point к источнику.

Подробнее и C++ Пример here

+0

благодаря марко, не могли бы вы размещая обновления на псевдокоде здесь? – Roy

+1

@Roy Здесь вы находитесь. –

1

Вам нужно добавить код после строки 17:

1 function Dijkstra(Graph, source, destination): 
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   if source = destination: 
19    return dist[], prev[]    // Valid only for destination vertex and vertex with lower distance 
20   
21   for each neighbor v of u:   // where v is still in Q. 
22    alt ← dist[u] + length(u, v) 
23    if alt < dist[v]:    // A shorter path to v has been found 
24     dist[v] ← alt 
25     prev[v] ← u 
26 
27  return dist[], prev[] 
+1

достаточно справедливо, но мы не можем сравнивать source = destination, поскольку источник никогда не изменяется. Возможно, вы имели в виду, если u = пункт назначения? – Roy

+1

и почему вы решили вернуться в этот момент и выйти из цикла. Поскольку в конце есть оператор возврата, мы можем сохранить дополнительную строку кода. – Roy

+0

Да, конечно, я имею в виду 'if u = destination', и заменить' return' на 'break' - хорошая идея. –

Смежные вопросы