Hands-On Software Engineering with Golang

Searching graphs for the shortest path

If we look around, we are bound to encounter a plethora of quite challenging problems that essentially boil down to finding a path or set of paths within a graph that minimize a particular cost function. Pathfinding has a multitude of real-world use cases, ranging from building efficient computer networks to logistics and even games!

The definition of a suitable cost function and its interpretation is typically application-specific. For instance, in the context of a map service, the cost associated with a graph edge could reflect the distance between two points or the time that's required to drive from one point to another due to traffic congestion. On the other hand, if we were talking about packet ...