1 Replies - 1261 Views - Last Post: 22 July 2016 - 10:18 PM

#1 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 63
  • Joined: 18-June 16

Graph road map problem

Posted 22 July 2016 - 10:12 PM

I'm not sure where to start or what to do for this homework problem. Can someone give me some help?

A region contains a number of towns connected by roads. Each road is labeled by the average number of minutes required for a fire engine to travel to it. Each intersection is labeled with a circle. Suppose that you work for a city that has decided to place a fire station at location G.

Graph: http://imgur.com/a/nz3Ck

b) Suppose one ”optimal” location (maybe instead of G) must be selected for the fire station such that it minimizes the distance to the farthest intersection. Devise an algorithm to solve this problem given an arbitrary road map. Analyze the time complexity of your algorithm when there are f possible locations for the fire station (which must be at one of the intersections) and r possible roads.

Is This A Good Question/Topic? 0
  • +

Replies To: Graph road map problem

#2 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12176
  • View blog
  • Posts: 45,243
  • Joined: 27-December 08

Re: Graph road map problem

Posted 22 July 2016 - 10:18 PM

You can reduce this to the All-Pairs Shortest Paths problem. Since this is a homework problem for what looks like an Algorithms class, this should hopefully give you an idea of where to begin in your notes/textbook.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1