Programming #6: Shortest Path Problem

Now that we have some of the programming basics under our belt, we can start using them to solve problems. Let’s start with one of the most famous problems in computer science, the shortest path problem.

As the name implies, the shortest path problem is about finding the shortest path in a graph. Imagine that we have a graph that represents our home town. Vertices or nodes would represent locations, and edges would represent streets connecting those locations. For simplicity, let’s say that each street goes both directions (undirected graph). We can also add weights to each edge that tell us the distance between two locations along a a given street. In this example, the shortest path would be the path between two locations, where the sum of the distance between streets is as small as possible.

Continue reading “Programming #6: Shortest Path Problem”

Advertisements