Question

Considering Google Maps as a graph, list four possible weights that can be associated with edges of the graph.

Answer 1

Considering Google Maps as a Graph, Google Maps must have been using a complex set of attributes to assign weights to the edges.

Edges, here, are nothing but, roads or to be more specific, paths(the path between New York and England are not connected via roads). Two places may be connected by a clean and straight pathway or they may be connected by a network of roads, turns, etc.

So, according to how optimal or how effective the path provided by Google Maps is, there can be a number of attributes that we can assign to the paths. We will design our function for determining weight.

Here is the list of 4 such attributes (and why?) :

1. Distance: We cannot consider the distance between the two places marked on a map. We need to consider the full distance, the actual path distance, the alleys that will come in the way, the turns that need to be taken, all that needs to be covered and hence, adds up to the final distance from the source to the destination. This is significant measure that can be taken as the "weight" of the edge while finding the optimal route, the user certainly would want to take the smallest path possible.

2. Traffic: Traffic is one of the major attribute that must be considered as the "weight" of the edge. The user certainly want to have a smooth drive to reach the destination. Traffic is unpredictable, it can easily turn minutes to hours. And even if we don't consider the checking stops, speed breakers and other stoppages, it is a major attribute that must be taken.

3. Number of Crossroads and Traffic lights: Crossroads are another time consuming places, that must have a part in the weight of the graph. The path with less number of crossroads means less traffic lights, less stoppage, hence, will be preferred. Crossroads too, can become a source of traffic, which makes it a part of the weight function.

4. Features of the Path: Not all paths are built the same. Some paths may have potholes(holes formed on the road using traffic), ruts(deep, narrow marks on the roads), etc, and they are the source of decreased speed and therefore, wasting time, bad experience. The user will obviously prefer to go from a smooth road path rather than the one filled with holes. Maybe not in the whole world, bad roads can certainly be the part of the weight function.

So, that compiles the different types of weights that can be associated with edges of the graph, in no specific order.

Please note that there can a number of other weights possible and that the weights mentioned here may or may not work in a certain place.