Hi everyone! In today’s lesson, we will see how to build routing tables to navigate a graph, using the spanning trees obtained from graph traversal algorithms, such as the BFS or the DFS.
These routing tables will help the artificial intelligence that you will develop in this course to move between two positions in the maze.
From spanning trees to routing
Routing from a starting point to a destination is interpreted backwards. We already know what the starting point is, so we need to begin with the destination to find a path. So, a routing algorithm provides a path from the destination to the starting point.
This second way of thinking is how the routing algorithm will work.
Routing from to any other vertex can be easy when we use trees. But to do this, we first need a few more definitions.
We can now build routing tables by considering the parent of each vertex in the path from . Routing tables are useful data structures that can be used to reconstruct a path. As we mentioned earlier, routing is considered backwards, from the destination back to the starting position.
Let us now see how this table is built step by step using a spanning tree.
To read this table, you can simply start from the desired destination and read the corresponding entry, which refers to the parent vertex of the destination.
As a second example, let’s also build the routing table from the spanning tree obtained from a BFS.
That’s it for today. Thank you for your attention! I’ve really enjoyed talking about routing with you.
You should remember that it is not sufficient to build the spanning tree to navigate between vertices in the graph, but that you also need a routing algorithm.