Consider now the single-target widest path problem for undirected graphs:

Given: an undirected graph G = (V, E), edge widths c : E R, and nodes r, s V ,

Task: find a widest r-s-walk.

Show that this problem can be solved in linear time.

Hint: You can use the fact that the median of m numbers can be found in time O(m)