





"""simple docstring"""




from __future__ import annotations




class 				_a		:






				def __init__(				self	:					Optional[Any],				lowerCAmelCase__	:					int							)			->   None:




										'''simple docstring'''



										_UpperCamelCase    :      Tuple						     =					vertices
										_UpperCamelCase    :      Optional[int]						     =					[[0] * vertices for _ in range(lowerCAmelCase__							)]






				def        snake_case			(				self	:					Union[str, Any],				lowerCAmelCase__	:					list[int]							)			->   None:




										'''simple docstring'''



										print('''Vertex \t Distance from Source'''							)
										for vertex in range(self.vertices							):
																print(lowerCAmelCase__,				'''\t\t''',				distances_from_source[vertex]							)






				def        snake_case			(				self	:					Dict,				lowerCAmelCase__	:					list[int],				lowerCAmelCase__	:					list[bool]							)			->   int:




										'''simple docstring'''



										_UpperCamelCase    :      Optional[Any]						     =					1e7
										_UpperCamelCase    :      Dict						     =					0

										# Search not nearest vertex not in the shortest path tree
										for vertex in range(self.vertices							):
																if distances_from_source[vertex] < minimum and visited[vertex] is False:
																						_UpperCamelCase    :      List[Any]						     =					distances_from_source[vertex]
																						_UpperCamelCase    :      Union[str, Any]						     =					vertex
										return min_index






				def        snake_case			(				self	:					Any,				lowerCAmelCase__	:					int							)			->   None:




										'''simple docstring'''



										_UpperCamelCase    :      List[str]						     =					[int(1e7							)] * self.vertices  # distances from the source
										_UpperCamelCase    :      Optional[int]						     =					0
										_UpperCamelCase    :      Dict						     =					[False] * self.vertices

										for _ in range(self.vertices							):
																_UpperCamelCase    :      int						     =					self.minimum_distance(lowerCAmelCase__,				lowerCAmelCase__							)
																_UpperCamelCase    :      Optional[int]						     =					True

																# Update dist value of the adjacent vertices
																# of the picked vertex only if the current
																# distance is greater than new distance and
																# the vertex in not in the shortest path tree
																for v in range(self.vertices							):
																						if (
																						    self.graph[u][v] > 0
																						    and visited[v] is False
																						    and distances[v] > distances[u] + self.graph[u][v]
																						):
																												_UpperCamelCase    :      Tuple						     =					distances[u] + self.graph[u][v]

										self.print_solution(lowerCAmelCase__							)


if __name__ == "__main__":
						UpperCamelCase_     =Graph(9)
						UpperCamelCase_     =[
						    [0, 4, 0, 0, 0, 0, 0, 8, 0],
						    [4, 0, 8, 0, 0, 0, 0, 11, 0],
						    [0, 8, 0, 7, 0, 4, 0, 0, 2],
						    [0, 0, 7, 0, 9, 14, 0, 0, 0],
						    [0, 0, 0, 9, 0, 10, 0, 0, 0],
						    [0, 0, 4, 14, 10, 0, 2, 0, 0],
						    [0, 0, 0, 0, 0, 2, 0, 1, 6],
						    [8, 11, 0, 0, 0, 0, 1, 0, 7],
						    [0, 0, 2, 0, 0, 0, 6, 7, 0],
						]
						graph.dijkstra(0)










"""simple docstring"""




def  a_       (							_lowercase     ):
						_UpperCamelCase    :      str						     =					len(_lowercase     )

						# Set the gap value to be decreased by a factor of 1.3
						# after each iteration
						_UpperCamelCase    :      str						     =					1.3

						# Continue sorting until the gap is 1
						while gap > 1:
												# Decrease the gap value
												_UpperCamelCase    :      Union[str, Any]						     =					int(gap / shrink     )

												# Sort the elements using insertion sort
												for i in range(_lowercase ,		len(_lowercase     )     ):
																		_UpperCamelCase    :      Optional[Any]						     =					collection[i]
																		_UpperCamelCase    :      int						     =					i
																		while j >= gap and collection[j - gap] > temp:
																								_UpperCamelCase    :      List[str]						     =					collection[j - gap]
																								j -= gap
																		_UpperCamelCase    :      Union[str, Any]						     =					temp

						return collection


if __name__ == "__main__":
						import doctest

						doctest.testmod()



