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.

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 O(VE)O(|V||E|) (where VV is the number of vertices, and EE 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.