6

My question is as follows: According to different sources, Dijkstra's algorithm is nothing but a variant of Uniform Cost Search. We know that Dijkstra's algorithm finds the shortest path between a source and all destinations ( single-source ). However, we can always modify Dijkstra to find the the shortest path between a START and a GOAL state ( when the goal is popped from the priority queue, we simply stop); but doing so, the worst case scenario will be still finding the shortest path from START to all other nodes ( suppose the goal is the furthest node in the graph).

If we implement Dijkstra's algorithm using a min-priority heap, the running time will be O(V log V +E) , where E is the number of edges and V the number of vertices.

Since Uniform Cost Search is the same as Dijkstra ( slightly different implementation), then the running time of UCS should be similar to Dijkstra, right? However, according to my AI class, Uniform Cost Search is exponential at the worst case, and it takes O(b1 + [C*/ε]), where C* is the cost of the optimal solution. ( b is the branching factor)

How can both algorithms be the same while they have different running times? Is the running time the same, but the way we look at it is different?

I would appreciate your help :):) Thank you

Chungmin Lee
  • 2,320
  • 2
  • 18
  • 19
John
  • 627
  • 10
  • 18

1 Answers1

3

Is the running time the same, but the way we look at it is different?

Yes. Uniform cost search can be used on infinitely large graphs, on which Dijkstra's original algorithm would never terminate. In such situations, it's no use defining complexity in terms of V and E as both might be infinite and the resulting big-O figure meaningless.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 1
    Let's stick to finite graphs ( maybe veeeeery large, but still finate). then how can I prove that both algorithms have the same running time? – John Oct 19 '12 at 15:08
  • 1
    @John: by rewriting the pseudocode of either algorithm until you find the other. That can be tricky because Dijkstra's is usually presented for finite graphs stored entirely in memory, but UCS for potentially infinite ones represented as edge generation functions. – Fred Foo Oct 19 '12 at 15:18
  • 1
    I agree with what you said, but in my case, here what I want to prove: given a map of cities ( a graph), I want to prove that both algorithms have the same time complexity to find the optimal solution – John Oct 19 '12 at 15:22