What are weighted graphs used for?


#1

Question

In the context of this exercise, what are weighted graphs used for?

Answer

Weighted graphs are used for applications where we need to take into account some cost or measurement between vertices of the graph.

For example, the weights can represent the time it costs to travel from one location to another. Or, they can represent a measurement, such as the distance between the locations. Using these weights, we can figure things out like the path that takes the least time, or the path with the least overall distance. This is a simplification of how weighted graphs can be used for more complex things like a GPS system.

We might even want to find the path that maximizes some value, rather than minimizes it. For instance, maximum flow problems are problems that seek to find what paths can give the highest total flow, such as for water or for networking.