dynamic - Shortest path algorithm design -

I am currently studying for the final and the following is a problem in the study guide:

" Create an O (K (M + N) time using the graphic programming technique using the least path algorithm, define optimal structure (G). The smallest path to the edge of K in a graph. "

Being on this is on the study guide, I'm sure it will not be at the last but I I am a little disturbed by the fact that I am not sure how to do this.

Is there any existing algorithms with this sequence that I should know? If not, how can I make an optimum solution? Right now I am implementing DjCastro's algorithm in Java, which has helped it to understand something, but I know that it does not meet the requirement of time, so I am thinking that I can adapt it. >

The question is basically asking (when K = N-1). You can define DP repetition:

Path [K] [V] is the shortest route leading up to the top, with maximum K is the edge. Now the smallest path to the maximum variance on which maximum Kashmir is the edge, it can be one of two possibilities. Either this path is similar to [K-1] [v] and it's length is of -1 or it uses an extra edge in the graph that v.

then it is repetitive

path [k] [v] = min (path [k-1] [v], path [k-1] [u ] + The cost of shore -> V all the edges of which through any upper part v)

Thus (K * (N + M)) in time K- Longest path, follow this pseudo-path.

Start the values ​​with values ​​from "source" to min at the other // In the corner there are 0 edges (for int i = 0; i & lt; n; i + +) {Path [0] [i] = Infinity; } Path [0] [source] = 0; // problem for DP solution below For (int i = 1; i & lt; = K; i ++) {for (edge ​​e: graph) {int u = e.from; Int v = e.to; Path [i] [v] = minutes (path [i-1] [v], path [i-1] [u] + e.cost); }}

Running time: External loop runs for K time and it checks all the edges in the graph. This is the time to run O (K (N + M)) .