Dive into NumPy! Start organizing, rearranging, and sampling your data.

Python Data Analysis and Visualization

From Python to Numpy

### 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(|V||E|)$ (where $V$ is the number of vertices, and $E$ 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.

# 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(|V||E|)$ (where $V$ is the number of vertices, and $E$ 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.

In this lesson, we will implement the solution of finding the shortest path in the maze using the Bellman-Ford approach. 

Introduction

Anatomy of an Array

Code Vectorization

Problem Vectorization

Custom Vectorization

Beyond NumPy

Coding Example: Find shortest path in a maze (Bellman-Ford approach)

Bellman-Ford Algorithm