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