JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Dynamic Programming: From novice to advanced | Reply
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

I've read this toutorial but I have a problem with the practice problem in the elementary section.
Here is the problem statement:

"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. "

Please help me to understand the problem statement and then introduce me a DP solution to solve it!

Thanks a lot...
Re: Dynamic Programming: From novice to advanced (response to post by Blackwizard) | Reply
If I'm reading the problem statement right, it's just a single-source shortest paths problem in a positive weights graph. You can solve this with Dijkstra's algorithm. The algorithm does use dynamic programming, but I don't really consider it very representative of how dynamic programming problems look like in competition programming.

However, in it's own right, the algorithm is important enough for you to get very familiar with it because it is useful for solving many problems.
Re: Dynamic Programming: From novice to advanced (response to post by buda) | Reply
Thanks to answer me and your advice!
Re: Dynamic Programming: From novice to advanced (response to post by buda) | Reply
But Dijkstra is used in directed positive weighted graph for finding shortest, this example is an undirected one, I was wondering if it is okay...
Re: Dynamic Programming: From novice to advanced (response to post by Auston) | Reply
Dijkstra's algorithm works for undirected graphs as well (you can reduce it to the undirected case by just using the same edge cost in both directions). In fact, that's how it was originally stated, as you can see by the n*(n-1)/2 upper bound on the number of edges mentioned at the end of the first page.
RSS