Finding Shortest Paths with Brute Force
As we laid out in the previous section, we will seek a path from vertex vi to vertex vj with a minimal sum of edge weights. Let's look at the prospects of finding the shortest paths using brute force.
For example, consider the following network that we discussed in Chapter 8, Storage and Feature Extraction of Graphs, Trees, and Networks. We will let V be the set of vertices, E be the set of edges, and W be the set of weights:
Figure 9.7 – A network
An example problem that we will try to solve is to find the shortest path from v1 to v2. There are many paths between these two vertices, which we list as follows along with their lengths:
Figure 9.8 – All the paths from v1 to v2 and their lengths, excluding paths that revisit the same vertex
From this full list of paths from v1 to v2, we can easily see that the shortest paths are the ones in the highlighted rows with lengths...
