[JustForFunAlgorithm]Shortest Path Finding using Floyd Algorithm

Hi, looooong time no see, and thrilled to see you again!

Let’s check the shortest pathfinding problem, and solve it using Floyd algorithm. (This was prepared for my assignment for the class in school. I submitted with C code and later rewrote it in Python. I am sharing my Python version here!)

The input graph is the following. (I wrote this down, please bear with my bad handwriting,)

Directed graph presentation of the input

And, this can be written as following matrix format.

graph = [[0,2,INF,1,8],
         [6,0,3,2,INF],
         [INF, INF, 0, 4, INF],
         [INF, INF, 2,0,3],
         [3, INF, INF, INF, 0]]

If graph[i][j] = ‘INF’, this signifies that there are no possible routes between point i and j.

1. As there are five vertices, I will set up parameter V for that, and INF to be random maximum number. Let’s say 99999. And will import numpy library with an alias ‘np’.

V = 5
INF = 99999
import numpy as np

2. As the input and output will be in the form of a matrix table, I will make a special print function to print that out in visually satisfying ways.

3. And I will make a table to store distance values. For that, I will make a function that makes a zero square matrix.

4. And, this function is for the Floyd Algorithm.

And, the result is the following.

And, check this out, Floyd Algorithm page in Wikipedia!

Floyd-Warshall algorithm