JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Dynamic Programming: From novice to advanced Question on practice problem
 Question on practice problem | Reply I am struggling to understand the below practice problem on this page. It is not clear to me how this graph is represented. I am not sure what I am given here. I only know of a graph represented as an adjacency matrix and adjacency list. Can someone please help explain how the graph would be represented in order to run LIS on it to find the shortest path? My thought is to assume an adjacency matrix size NxN and run a shortest path on this somehow using LIS. I'm not sure if this is the right track or not.Thanks in advance for any help! Practice problem:Given an undirected graph G having N (1<=1000) vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesnÃ¢ÂÂt exist.Hint: At each step, among the vertices which werenÃ¢ÂÂt yet checked and for which a path from vertex 1 was found, take the one which has the shortest path, from vertex 1 to it, yet found.
 Re: Question on practice problem (response to post by zzkoder) | Reply Actually, shortest path problem is NOT related to longest increasing subsequence problem.You can use dijkstra's algorithm (dynamic programming solution) and it can solve for O(N^2).
 Forums Tutorial Discussions Dynamic Programming: From novice to advanced Question on practice problem Previous Thread  |  Next Thread