[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.

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’.

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!

--

--

Ydobon is nobody.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store