Member Search
|
|
Search
|
Watch Thread | My Post History | My Watches | User Settings View: Flat | Threaded | Tree Previous Thread | Next Thread |
||
Forums
Tutorial Discussions
Dynamic Programming: From novice to advanced
Dynamic Programming: From novice to advanced
|
||
| 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 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. | |
|
Forums
Tutorial Discussions
Dynamic Programming: From novice to advanced
Dynamic Programming: From novice to advanced
Previous Thread | Next Thread |
 |