Question

This is a graph problem. Sandy lives in the city, 'S', and Tom lives in the city, 'T'. Now, there is a city, 'M' where they can both meet so that the travel time minimized for both. How do we find the city, 'M' in a graph of cities where vertices represent cities and edge weight represent travel time between them?

Answer 1

The city M will be the city for which the absolute difference between the time taken by tom and sandy to travel to M is minimum

1)Use shortest path algorithm like dijkstras to find minimum time taken to travel from city S to all other cities and from city T to all other cities

2)Now traverse each city and find absolute value of time taken from city S to that city and time taken from city T to that city

3)The city for which the value calculated in above step is minimum is the answer.

pseudo code for dijkstras

Let graph be G(V,E)

function Dijkstra(G, s):

for each vertex v in Graph:

dist[v] = inf //set distance to each city as infinity

dist[s] = 0 //distance of source is 0

Q =V

while Q is not empty

u = node with minimum dist[]

Q.remove(u)

for v neighbour u and v is in Q

dist[v]=min(dist[v],dist[u]+distance_between(u,v)) / /where v has not yet been removed from Q.

return dist[]

dist_from_T=dijkstra(G,T)

dist_from_S=dijkstra(G,S)

ans=1//assuming the optimum city is 1st city

for each city in G

if abs(dist_from_T[city]-dist_from_S[city]))<abs(dist_from_T[ans]-dist_from_S[ans]))

ans=city

print ans

If you have more doubt please connect in comment section.Please do upvote