Challenge Problem: Implement Floyd$-$Warshall

In this challenge problem, you will investigate and implement the Floyd$-$Warshall dynamic programming algorithm for finding all$-$pairs shortest paths. Preferably Programmed in python

Learning Objectives

$-$ Topics: Dynamic Programming, Graph Algorithms.

$-$ Pair Project: No

Instructions

One problem with Dijkstra's Algorithm for finding shortest paths is that it cannot handle edges with negative weights. The Floyd$-$Warshall algorithm solves this problem in an interesting way using Dynamic Programming. The algorithm asks "What is the shortest path from A to B using only the first K indexes as possible intermediate vertices?" Thus, a base case with $\backslash (\backslash$mathrm$\{$K$\}=0\backslash )$ is precisely the starting graph.

Read section $8\mathrm{.}4$ in the textbook $($the textbook refers to this algorithm as "Floyd's Algorithm"$).$ Then implement in code the Floyd$-$Warshall algorithm for all$-$pairs$-$shortest$-$paths.

Along with the implementation itself, I would like to see a brief demonstration using a graph of your choosing.

Submission Instructions

Please submit your code, along with your estimate for how much time you spent on this assignment$*$