What is the purpose of the visited set in Dijkstra?

Question

On the Wikipedia page for Dijkstra's algorithm, they mark visited nodes so they wouldn't be added to the queue again. However, if a node is visited then there can be no distance to that node that is shorter, so doesn't the check alt < dist[v] already account for visited nodes? Am I misunderstanding something about the visited set?

for each neighbor v of u:   
      alt := dist[u] + dist_between(u, v);          // accumulate shortest dist from source
      if alt < dist[v] && !visited[v]:                                 
          dist[v]  := alt;                          // keep the shortest dist from src to v
          previous[v]  := u;
          insert v into Q;                          // Add unvisited v into the Q to be processed
      end if
  end for

Macaroni

Answer 1

There are actually 2 sets you need to consider:

• The visited set
• The queued set

The visited set

The visited set contains those vertices which have been popped from the queued set. These cannot be re-visited because by definition, the shortest path from the start to these vertices has already been discovered

The queued set

The queued set contains unexplored vertices queued in order of shortest-distance-to the start vertex. This queue is usually represented using a (min)heap structure.

---

Explanation

Depending on the density of the graph, each vertex has a possibility of being a part of more than one edge. Note that an edge is the smallest component that connects a vertex to another vertex. Therefore, this implies possibility of having more than one vertex with an edge to the current vertex.

Each iteration of the outer loop of the Dijkstra's algorithm takes the vertex (from the queued set) with the smallest distance to the start vertex, and relaxes the edge cost to each vertex connected to it. If the vertex is already in the queued set, it's value and position in the queue is updated.

The reason alt < dist[v] is done is because it is possible to encounter a vertex that is already in the queue more than once so each time it is encountered you have to make sure that before you edit it's distance to the source vertex, it's current distance is larger than the new distance you want to assign to it (alt < dist[v]) and it is not processed as visited (!visited[v])

Shortest distance

• Dijkstra's algorithm by definition provides the guarantee that as soon as a node is marked as visited, the distance value of that node is the shortest to the source. If a node is marked as visited, this does not imply that the distance to the source from that node is the shortest distance in comparison to the distance from the source to any other node. Visited implies that the objective of Dijkstra's algorithm has been met for that node; i.e. it currently stores the smallest distance from the source to itself.

• If you completely want to discard checking for visited, then what you can do is that once you mark a node as visited, you iterate through all the edges connected to that node and delete them. This makes sure that any future nodes processed, does not have an edge that connects to any node marked as visited. However, because the graph is represented using an adjacency list, going with this option will be costly in terms of time; And depending on how dense the graph is, you would have been better off just having a visited set.
  If you represent your graph using an adjacency matrix, then the benefit of this is that the check will only cost O(N) time. However, adjacency matrix uses N² space vs N space of adjacency list, you will be paying the price for this in memory, which may or may not be so bad depending on the graph size.

Finally

Once you understand all this, you will come to see that everything done in the code is needed to produce the correct results.

Doubloon

If visited[v] = true, doesn't that imply that for any alt, alt < dist[v]? So isn't checking visited[v] not necessary? Since alt >= dist[v] implies !visited[v] – Macaroni

I think it should be noted that the visited set is only needed when you're not given the whole graph: only the starting vertex. If you're given the whole graph at the outset, you just add all the vertices to your queue and no longer have to decide whether an encountered vertex needs to be expanded or not. – Dworman

It seems visited is not needed. If the idea is to prevent an item of a bigger destination to be added to the queue, then then destination check and priority queue do a better job. – Publus

Answer 2

Yes, you're right. There's no need for the visited vector.

If a node is visited then there cannot exist a distance to that node that is shorter, so, as you said, checking alt < dist[v] is enough.

Take a look here:

Acquiesce

Why do they maintain it then? At various resources I found vis. is also there. Some purpose must be there I think. – Intervenient

Answer 3

You are right, alt < dist[v] already ensures that nodes that are relaxed to the fullest won't get pushed again.

The Visited set is an optimization to reduce the time complexity. Consider this example: (Assume there is no visited set)

Suppose for any unvisited node 7 we somehow got relaxation done 3 times. As a result (distance, relaxed node): (9, 7), (5, 7), (3, 7) get pushed inside the priority queue. Since the queue is sorted it gets stored in this order:

• ...some previous pairs
• (3, 7)
• (5, 7)
• (9, 7)

Now, when it comes to processing node 7, the first time it does with (3, 7), after going through its children, Dijkstra claims that the node is relaxed to the fullest. But our priority queue has two more entries with node 7: (5, 7) and (9, 7).

Without visited set, node 7 gets processed two more times, which is no use. To deal with this, we maintain the visited set, so we skip its following occurrences when node 7 is marked after first processing.

Oven

Answer 4

If we encounter a negative cycle, it might happen that alt < dist[v] would become true for a node that was already visited . But we dont have to consider negative cycles, and hence checking if the node is already visited is important.

Basis

dijkstra's algorithm doesn't work on a graph that has negative edges. So why to keep visited? – Mcgough