What's the difference between Modified Dijkstra with single source, single destination point and Uniform Cost Search?

Question

If we modify Dijkstra algorithm from "single source to all nodes shortest path" to find the shortest path from "single source to a single destination point", then what will be the difference between this modified Dijkstra and uniform cost search? Any help will be appreciated. Thanks.

Answer 1

A very good dissection of the differences between both algorithms can be seen in Dijkstra’s Algorithm versus Uniform Cost Search or a Case Against Dijkstra’s Algorithm. I just quote you some of the conclusions from Arial Felner:

The two algorithms have many similarities and are logically equivalent. The most important similarity is that they expand exactly the same nodes and in exactly the same order.

As we suspect, both algorithms are equivalent from the theoretical point of view.

However, there are many differences between these algorithms as described in text books and taught in classes. The main difference is the identity of the nodes in the priority queue. In modified Dijkstra, all nodes are initially inserted into the queue. In UCS, nodes are inserted to the queue lazily during the search.

---

Thus,

1. In terms of memory requirements they are different, OPEN of UCS is much smaller than the Q of modified Dijkstra. At any given time step, the memory need of modified Dijkstra is larger than that of UCS.
2. In terms of running time, the same reasoning applies to the time overhead of manipulating OPEN or Q. Modified Dijkstra has a bigger overhead manipulating these structures, since it stores nodes with dist[] = ∞, which will never be expanded. By contrast, in UCS, OPEN only includes nodes with dist ≠ ∞, i.e., only the nodes that are logically needed and might be chosen for expansion.

In summary, UCS and modified Dijkstra are equivalent in their big O complexity, expand the same nodes and in the same order, but UCS should be preferred from a practical point of view and it is more widely used when approach the single source - single destination problem without heuristic information.

Answer 2

There is no difference. If you use dijkstra, When you start from single source there will be calculated shortest path for all node. You visit from source node to connected node. Then next node is shortest cost node from priority queue. Before insert new node in priority queue, check current node cost and new cost. If new cost is less than node cost then insert this node in priority queue.

Look at this to get how to calculate single source to all node.