The Practitioner's Guide to Graph Data

Chapter 9. Finding Paths in Production

More often than not, the first concept we think about with paths is how many stops it takes to get from the start to the finish. This was the topic for Chapter 8.

The next concept when working with paths through graphs is to evolve the idea of distance. We do this by adding some type of weight or cost to steps along a path. We refer to this type of problem as a minimum cost path or a shortest weighted path.

Shortest weighted paths are very popular optimization problems in computer science and mathematics. These types of problems tend to be multifaceted, complex optimization problems because they are trying to combine more than one source of information into a cost metric for minimization.

We saw an example of a weighted path problem at the end of Chapter 8. We tried to find the most trusted path through our data by aggregating path weights. Because high trust in our sample data is represented by higher values, this type of pathfinding problem led to the discovery that higher trust paths are also longer paths through our data. This is not what we wanted.

Instead, we need to understand how to use edge weights to find shortest paths. Through the lenses of mathematics and computer science, we want to create a bounded minimum optimization problem.

In this sense, high trust is inversely correlated with path length. We want to find paths that are simultaneously short and have high trust. This is the difficult duality we are going to address and ...