




'''simple docstring'''





import math




class 			_snake_case		:




			def __init__( self    ,							a__=0							)    ->    Optional[Any]:  # a graph with Node 0,1,...,N-1

										'''simple docstring'''




										snake_case_      =				n
										snake_case_      =				[
										    [math.inf for j in range(0    ,							a__							)] for i in range(0    ,							a__							)
										]  # adjacency matrix for weight
										snake_case_      =				[
										    [math.inf for j in range(0    ,							a__							)] for i in range(0    ,							a__							)
										]  # dp[i][j] stores minimum distance from i to j




			def        lowerCAmelCase__    ( self    ,							a__    ,							a__    ,							a__							)    ->    List[Any]:

										'''simple docstring'''




										snake_case_      =				w




			def        lowerCAmelCase__    ( self							)    ->    Union[str, Any]:

										'''simple docstring'''




										for k in range(0    ,							self.n							):
																	for i in range(0    ,							self.n							):
																								for j in range(0    ,							self.n							):
																															snake_case_      =				min(self.dp[i][j]    ,							self.dp[i][k] + self.dp[k][j]							)




			def        lowerCAmelCase__    ( self    ,							a__    ,							a__							)    ->    str:

										'''simple docstring'''




										return self.dp[u][v]


if __name__ == "__main__":
		_SCREAMING_SNAKE_CASE							:       int						=			Graph(5)
		graph.add_edge(0, 2, 9)
		graph.add_edge(0, 4, 10)
		graph.add_edge(1, 3, 5)
		graph.add_edge(2, 3, 7)
		graph.add_edge(3, 0, 10)
		graph.add_edge(3, 1, 2)
		graph.add_edge(3, 2, 1)
		graph.add_edge(3, 4, 6)
		graph.add_edge(4, 1, 3)
		graph.add_edge(4, 2, 4)
		graph.add_edge(4, 3, 9)
		graph.floyd_warshall()
		graph.show_min(1, 4)
		graph.show_min(0, 3)









'''simple docstring'''





from __future__ import annotations

import numpy as np


def 					UpperCamelCase_(     snake_case							:	np.ndarray					):

							'''simple docstring'''






							snake_case_ ,				snake_case_      =				np.shape(snake_case					)
							if rows != columns:
														snake_case_      =				(
														    "'table' has to be of square shaped array but got a "
														    f'{rows}x{columns} array:\n{table}'
														)
														raise ValueError(snake_case					)

							snake_case_      =				np.zeros((rows, columns)					)
							snake_case_      =				np.zeros((rows, columns)					)
							for i in range(snake_case					):
														for j in range(snake_case					):
																					snake_case_      =				sum(lower[i][k] * upper[k][j] for k in range(snake_case					)					)
																					if upper[j][j] == 0:
																												raise ArithmeticError("No LU decomposition exists"					)
																					snake_case_      =				(table[i][j] - total) / upper[j][j]
														snake_case_      =				1
														for j in range(snake_case							,    snake_case					):
																					snake_case_      =				sum(lower[i][k] * upper[k][j] for k in range(snake_case					)					)
																					snake_case_      =				table[i][j] - total
							return lower, upper


if __name__ == "__main__":
		import doctest

		doctest.testmod()




