xennygrimmato's blog

Topcoder tutorial : Dynamic Programming
By xennygrimmato, 11 years ago, In English

I started learning Dynamic Programming today from Topcoder's tutorial. The following was put up as a Practice Problem:

Given an undirected graph G having N (1<N<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesn't exist.

My question is, 1. How does it matter, whether the graph is directed or undirected? 2. I can apply Dijkstra's algorithm directly on the graph, so what's the use of Dynamic Programming to solve this question?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

  1. Undirected graph is a special case of directed. This is for clarity only.

  2. It's just example for DP. And there are many algorithms to solve different problems with different usage of memory and time. Each has pros and cons. Will you use Dijkstra's algorithm, when you can use BFS?

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Dijkstra is a dynamic algorithm , so you can use it ...

+

with BFS algorithm , u can't find the shortest way !

BFS is O(E + N) and Dijkstra is O(e.log e) or O(n^2) ! if there is a solution with simple bfs , Why everybody use dijkstra ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dijkstra using heap is O(n log n + m) not O(m log m) (unless your implementation is not good) where n is number of vertices and m is number of edges so when we have complete graph (that means m=n^2) the complexity of dijkstra using heap is O(n log n + n^2) = O(n^2) so in case of complete graph complexity is not O(n^2 log n^2)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      My algorithm in worse case is O(n^2) too !

      if(m.log m < n^2) --> using Red Black Tree with O(m.log m)

      if(m.log m > n^2) --> a algorithm with O(n^2)

      so my algorithm is O(min(m.log m , n^2)) and dijkstra using fibonachi heap is O(n^2) in worse case !

      so your algorithm is not better than me ! good luck :D

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    BFS is not useful for weighted graphs , how we can use it ?

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A breadth-first-search only works in graphs with equivalent weight edges, and it's probably not the case. Try to think in a dp with states dp[current_iteration][i][j] as the shortest path from vertex 'i' to vertex 'j' in the current iteration.

→ Reply