Dijkstra source to destination shortest path in directed, weighted graph

Question

In the wiki page on Dijkstra, I am informed that if destination is known, I can terminate the search after line 13. I don't get this, how do I terminate the search after line 13?

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

Answer 1

You need to add some code after line 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[]

Answer 2

Wikipedia is wrong, the right line is 16 in that algorithm. An edit probably spoiled the line numbers or the paragraph below them.

What the paragraph meant is that if you're only interested in the shortest path from vertex S to Q, you can safely get out of the loop when Q is found since any other path will have a cost higher to reach it. Pseudocode follows

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

When you encounter the end point Q, you can safely skip the update part where you update any adjacent vertex with a shortest path to reach it -> you've already found your destination. To reconstruct the path simply reverse walk the vector prev from destination_point to the source.

More details and a C++ example here