Finding one’s way in a graph is the first topic I came across when learning how to program. The answer looked simple: use Djikstra’s beautiful algorithm – but there is more to it.
The simplest pathfinding you can do
The context here is a graph, whose nodes are linked by edges. Which algorithms can help us find how to go from node A to node B? Most people know about those graph traversal algorithms:
- Breadth-first search (BFS) minimizes the number of hops.
- Djikstra enables the use of weights. In some settings, it makes sense to explore less of the graph by running a bi-directional search. It can can save about 50% of the search effort. If you implement it, check your termination conditions, it is trickier than it seems..!
Specialized pathfinding needs
- What happens when your graph is allowed negative weights? This is a big concern for general graphs, solved by the Bellman-Ford algorithm.
- Computing shortest distances between all points can be needed, and is typically done by Floyd-Warshall.
Redundant shortest paths for telecom networks
In telecom networks the need for diverse redundant routes leads to computing k-shortest paths. If a fiber fails, we still want a “protection” over which the connection will switch to. The backup path should be either edge or node disjoint. Most often, Yen’s algorithm or Suurballe’s are used.
These works well when provisionning new incremental resources, but when designing doing global network optimization, you often shortlists of decent K paths/pairs to feed into a solver. To compute those shortlists, brute-force is usually a very good approach. Let’s be honest, telecom physicall network are not that big!
Graph representations for pathfinding
Choosing an adequate graph representation can already make you answer a lot of questions1: is your graph undirected? Will your graph need to be updated? How sparse is it? Do you want fast adjacency queries?
The usual choices are representing your graph using adjacency lists and adjacency matrices, best for sparse graphs2. Using sparse adjacency matrices is not always straightforward.
In addition, if you setup a algorithmic pipeline, chances are you will need to spend some time converting your graphs from one format to the other: graph data-structures are often custom-made for a particular application. You graph may need to be enriched to deal with application-specific concepts (think turn-by-turn navigation, various constraints…)
For the next article in the series, we’ll see what happens when we think of the graph nodes as points on map. Meet pathfinding for road networks!
Speaking of implementation, even writing a priority queue for Djikstra can make you review your computer science basics. ↩︎
Fact: The average degree of a node in road networks is 2.5. ↩︎