Coding Example: Find shortest path in a maze (Bellman-Ford approach)
In this lesson, we will implement the solution of finding the shortest path in the maze using the Bellman-Ford approach.
We'll cover the following
Bellman-Ford Algorithm
The Bellman–Ford algorithm is an algorithm that is able to find the optimal path in a graph using a diffusion process. The optimal path is found by ascending the resulting gradient. This algorithm runs in quadratic time (where is the number of vertices, and is the number of edges).
However, in our simple case, we won’t hit the worst case scenario. Once this is done, we can ascend the gradient from the starting node. You can check on the figure that this leads to the shortest path.
Get hands-on with 1400+ tech skills courses.