Dijkstra's algorithm for directed graph with positive weights and a cycle

Question

If I have a directed graph with a cycle and only positive weights, and instead of using Priority Queue, I use a queue and keep adding all children, including those that were visited because I choose not to track the visited, can my algo fall in infinite loop? I am unable to develop the intuition for this and also not sure if my understanding is correct.

Answer 1

For this consider the following graph:

and consider the pseudo code, whithout tracking the visited nodes.

 1  function Dijkstra(Graph, source):
  2      
  3      for each vertex v in Graph.Vertices:
  4          dist[v] ← INFINITY
  5          prev[v] ← UNDEFINED
  6          add v to Q
  7      dist[source] ← 0
  8      
  9      while Q is not empty:
 10          u ← Q.pop()
 11          remove u from Q
 12          
 13          for each neighbor v of u still in Q:
 14              alt ← dist[u] + Graph.Edges(u, v)
 15              if alt < dist[v]:
 16                  dist[v] ← alt
 17                  prev[v] ← u
 18                  add v to Q
 19
 20      return dist[], prev[]

We know we have a cycle and assume that the edges have weights larger than zero. By the algorithm, we know after at most 2 steps we are in the cycle starting with B. Scanning its neighbors, C, and updating its distance and adding its neigbors again. Doing this until the current node is E. By this point, we know that the distance from E is smaller than infinity and we have D and F in the queue. We again update the distance of F, add its neigbors(which is empty) and update the distance of D. If we again add the neigbors of D to the queue, we have B in the queue. In line 18 we can see that we are only adding nodes to the queue, if the distance of the previous node is smaller than the current distance of B. Since, we only have edge weights larger than 0, there is no possibility that the distance of D is smaller than distance of B. Hence, we are than not adding any further nodes to the queue, which will leave it empty. If the queue is empty, the algorithm will terminate. If we, e.g. would slightly modify the algorithm, s.t. we always its neighbors to the queue, yes there can be cases, in which the algorithm doesn´t terminate. But this only the case, if we don´t check if the distance is smaller or not keep track of the visited nodes.

Long story short:

If you have something to keep track of the current state of the procedure, let it be the distance of the node or which node was visited etc., you won´t run into any endless loop. Unless the edges weights are negative.