Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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<N><=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).