N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same pair of houses.
They decided to meet so they want to
Choose a point(not necessarily an integer) P on the road numbered K, such that, the maximum of dist(i) for all 1≤i≤N is minimised,
where dist(i) is the shortest distance between the i'th friend and P.
If K'th road connects friend A and friend B we need to find distance of chosen point from A. Also, we need the max(dist(i)) for all 1≤i≤N.
Note : If there is more than one solution, we need to find the one in which the point P is closest to A.
Example : Let their are 4 friends and 4 roads connecting them as follow : (Next 4 lines are of format A B C which depicts that A and B are connected by a road C unit in length.)
1 2 10
2 3 10
3 4 1
4 1 5
Here answer is The distance of P from the point A = 2.00 and the maximum of all the possible shortest paths between P and all friends' houses = 8.00
Explanation : As K = 1, they will meet at a point P on the road connecting friend 1 and friend 2. If we choose point at a distance of 2 from friend 1: Friend 1 will have to travel distance 2. Friend 2 will have to travel distance 8. Friend 3 will have to travel distance 8. Friend 4 will have to travel distance 7. So, the maximum will be 8. In any other position of point choosen, the maximum distance will be more than 8.
So given N,M,K and M roads how to do this problem?Please help
The problem you describe is a specialization of the 1-center problem on graphs. This problem can be mathematically formulated as follows: Given a graph $G = (V, E)$ with node set $V$ and edge set $E \subseteq V \times V$ with distances $d: E \rightarrow \mathbb{R}$, find the point $x$ in the graph minimizing \begin{align} \max_{v \in V} d(v, x) \end{align} The solution of your example already demonstrates a property that every optimal solution of the 1-center problem fulfills: Your solution $P$ has the same distance to node two nodes (in your case friend $2$ and friend $3$). Let us call such a point an equilibrium point. If you consider a solution inside an edge that has a different distance to all nodes and is, thus, no equilibrium point, then you can improve the maximal distance by moving towards one of the end points of the edge.
Thus, you can solve the 1-center problem by enumerating all equilibrium points and all nodes and comparing the objective values of them.
How do you compute the equilibrium points? For each pair of nodes $u \in V$ and $v \in V$ and each edge $(w_1, w_2) = e \in E$ you can compute the point $x \in e$ with $d(u, x) = d(x, v)$ if such a point exists. Let $x = u + \lambda (v - u)$ for $\lambda \in [0,1]$. Then we have \begin{align} d(u, x) = \min\{d(u, w_1) + \lambda d(e), d(u, w_2) + (1 - \lambda) d(e)\} \\ d(v, x) = \min\{d(v, w_1) + \lambda d(e), d(v, w_2) + (1 - \lambda) d(e)\} \end{align} The two possible intersection points of these two piecewise linear functions are given by \begin{align} \lambda_1 = \frac{d(v, w_2) - d(u, w_1) + d(e)}{2 \cdot d(e)} \end{align} and \begin{align} \lambda_2 = \frac{d(u, w_2) - d(v, w_1) + d(e)}{2 \cdot d(e)} \end{align} In your example we have $u = 2$, $v = 3$ and $e = (w_1, w_2) = (1, 2)$. This gives \begin{align} d(u, w_1) &= 10 & d(u, w_2) &= 0 & d(e) &= 10 \\ d(v, w_1) &= 6 & d(v, w_2) &= 10 \\ \end{align} which results in \begin{align} \lambda_1 &= \frac{10-10+10}{2 \cdot 10} = 0.5 \\ \lambda_2 &= \frac{0-6+10}{2 \cdot 10} = 0.2 \end{align} The point $P$ in your example corresponds to $\lambda_2$ and has a distance of $8$ to nodes $2$ and $3$. The point corresponding to $\lambda_1$ does not give a equilibrium point because it is found using $d(u, x) = d(u, w_1) + \lambda d(e) = 10 + 5$ which is greater than $d(u, w_2) + (1 - \lambda) d(e) = 0 + 5$.
In your problem you are only looking for those solutions that are contained in a given edge. Thus, you would only consider the equilibrium points on this edge and the two end points.