Page 1 of 1

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

### #1 harro.rm

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

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

• Games, Graphs, and Auctions

Reputation: 12223
• Posts: 45,299
• 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.