Kurt Peek khpeek

I'm a Software Engineer with a background in Mathematics and Physics.

khpeek / floyd_warshall.py

Created September 18, 2017 16:42

Python implementation of the Floyd-Warshall algorithm as described in Section 25.2 of Cormen et al., Introduction to Algorithms (3rd ed.)

	import numpy as np
	from cached_property import cached_property
	import pytest


	class Graph(object):
	'''Solve the all-pairs shortest-path (APSP) problem using the Floyd-Warshall algorithm as described
	in Section 25.2 of Cormen et al., Introduction to Algorithms (3rd ed.). The implementation is directly
	from the pseudocode given there; in particular, there is no space optimization, and only the weights
	of the shortest paths are computed; no predecessor pointers are stored to reconstruct the shortest paths.'''