Search code examples
graph-theoryuniform-cost-search

UCS algorithm iteration

I've been trying to implement UCS and for that I thought it will be best if I first did hand sketch of how it work other than going through code. I got a graph

graph

I tried implementing the UCS(Uniform cost Search) in the above graph. But I got confused in the state when I have

Open nodes as : (V2,9),(V5,9),(V5,10),(V2,12),(V6,13)

closed nodes as: (V1,0),(V3,4),(V4,5),(V2,6)

Do I have to include (V2,9) in the open nodes as (V2,6) is already in the closed nodes?.

I tried looking different articles on that and each giving me different answers. Some say include it while other say don't.

Solution

  • That depends on how's your priority queue implemented. There's basically two options:

    (1) A node can't be present more than once in the queue. When visiting a node, if you find a shorter path to an adjacent node that's already in the queue, you update its priority based on the newly found path (if it's shorter).

    In this case, the queue entry (V2,9) has already been replaced by (V2,6) after visiting node V3. (V2,12) will never be added to the queue, as V2 is already present in the queue with a higher priority when visiting V4.

    (2) You don't enforce uniqueness for the nodes in the queue. When getting the entry from the queue, you check whether the node has already been visited (= it's in what you call closed nodes) and you skip it in such case.

    In this case, the queue contains entries (V2,9),(V5,9),(V5,10),(V2,12),(V6,13) (as you stated in your question). You skip V2 as it has already been visited and visit V5.

    In any case, a node is never added to the queue after it has been visited, otherwise the algorithm wouldn't stop.