CODEWITHSUNDEEP
algorithmdata-structurestree
Deadly Nicotine
Deadly Nicotine

Reputation: 663

Djikstra's algorithm: Do I iterate through the neighbors or the children?

I'm looking at Djikstra's algorithm in pseudo-code on Wikipedia

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Source node will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

and the part that's confusing me is line 16. It says for each neighbor but shouldn't that be for each child (i.e. for each neighbor where neighbor != parent). Otherwise I don't see the point of setting the parent in line 20.

Upvotes: 0

Views: 302

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

Ultimately, Dijkstra's algorithm computes something called a shortest-path tree, a tree structure rooted at some starting node where the paths in the tree give the shortest paths to each node in the graph. The logic you're seeing that sets the parent of each node is the part of Dijkstra's algorithm that builds the tree one node at a time.

Although Dijkstra's algorithm builds the shortest-path tree, it doesn't walk over it. Rather, it works by processing the nodes of the original path in a particular order, constantly updating candidate distances of nodes adjacent to processed nodes. This means that in the pseudocode, the logic that says "loop over all the adjacent nodes" is correct because it means "loop over all the adjacent nodes in the original graph." It wouldn't work to iterate over all the child nodes in the generated shortest-path tree because that tree hasn't been completely assembled at that point in the algorithm.

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76297

The previous node is set on line 20:

prev[v] ← u

This can only happen if line 14 is executed:

remove u from Q

So, for any v, prev[v] cannot be in Q - it was previously removed, and it will never return to Q (within the loop starting at 12, items are not added anymore to Q). This is the same as saying for any u, prev[u] cannot be in Q - asides from changing the name of the variable, it says the same thing.

In the question you say that about line 16:

it says for each neighbor

But, if you look at the pseudocode, it actually says

 for each neighbor v of u:           // where v is still in Q.

So, prev[u] will not be iterated over - it's not in Q.

For what it's worth, I think the pseudocode is a bit sloppy and confusing // where v is still in Q should not be a comment. It doesn't clarify or explain the rest of the code - it alters the meaning, and should be part of the code. Perhaps that confused you.

Upvotes: 1

Related Questions