Choosing the Right Approach

By now, it is probably apparent that there is rarely a single 'perfect' approach to implementing graph structures. The characteristics of the data we are representing, combined with the details of the problem we are trying to solve, can make certain approaches unreasonably inefficient, despite the fact that they may be perfectly acceptable under different sets of conditions.

Whenever you are trying to determine whether to use adjacency lists versus matrices, classes/structs versus simple arrays, Bellman-Ford versus Johnson's algorithm, BFS versus DFS, and so on, the final decision should be primarily dependent upon the specifics of the data and how you intend to use it. For example, if you want to find the shortest distances between every pair of nodes in a graph, Johnson's algorithm would be an excellent choice. However, if you only need to sporadically find the shortest distances for a single starting node, Johnson's algorithm would perform...