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?
Undirected graph is a special case of directed. This is for clarity only.
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?
Didnt even think of BFS :| Damn it.. Thank you.
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 ?
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)
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
BFS is not useful for weighted graphs , how we can use 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.