Revisiting the Shortest Path Problem

We previously discussed several ways to find the shortest path between two nodes in a graph. We began by exploring the most standard forms of graph traversal, namely depth-first search and breadth-first search, and eventually discussed how to approach the more problematic case of graphs containing weighted edges. We demonstrated how Dijkstra's algorithm could be used to efficiently find the shortest distances in weighted graphs by greedily prioritizing each step in the traversal according to the best option immediately available. However, despite the improvement in performance that Dijkstra's algorithm provides, it is not applicable to every situation.

Consider a Wi-Fi signal that is being broadcast through a network; as it travels beyond the point at which it is originally transmitted, its strength is likely to be affected by numerous factors, such as the distance it travels and the number of walls and other obstacles it must pass through. If...