CODEWITHSUNDEEP
algorithmpathdynamic-programmingdijkstrabellman-ford
Nick
Nick

Reputation: 31

Find the minimize maximum weights in weighted graph using dynamic programming

I'm looking for an algorithm that finds the path from two vertices say s to t, in a graph that has exactly k edges if paths exist.

And if multiple paths were found, the one with the minimum maximum weights of a single edge is preferred. (not the overall weights).

eg: say K = 5

Path 1: s - a - b - c - d - t with weights 1 - 1 - 1 - 10 - 1

the maximum weight of path 1 is 10

Path 2: s - x - y - z - w - t with weights 7 - 9 - 8 - 6 - 7

the maximum weight of path 2 is 9, so this is preferred.

How exactly do I solve this problem?

Upvotes: 3

Views: 1562

Answers (1)

hugomg
hugomg

Reputation: 69924

You could use a modified version of the Floyd-Warshal algorithm that only iterates for K steps and forces the path lengths (by removing the min part)

Upvotes: 2

Related Questions