

'''simple docstring'''

from __future__ import annotations


class   lowerCAmelCase     :







       def __init__(							self			: List[str]						,      __lowercase			: int      ):







            """simple docstring"""







            __lowercase					=vertices
            __lowercase					=[[0] * vertices for _ in range(__lowercase      )]







       def 			snake_case   (							self			: Tuple						,      __lowercase			: list[int]      ):







            """simple docstring"""







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







       def 			snake_case   (							self			: Union[str, Any]						,      __lowercase			: list[int]						,      __lowercase			: list[bool]      ):







            """simple docstring"""







            __lowercase					=1E7
            __lowercase					=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:
                      __lowercase					=distances_from_source[vertex]
                      __lowercase					=vertex
            return min_index







       def 			snake_case   (							self			: Union[str, Any]						,      __lowercase			: int      ):







            """simple docstring"""







            __lowercase					=[int(1E7      )] * self.vertices  # distances from the source
            __lowercase					=0
            __lowercase					=[False] * self.vertices

            for _ in range(self.vertices      ):
                 __lowercase					=self.minimum_distance(__lowercase						,      __lowercase      )
                 __lowercase					=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]
                      ):
                           __lowercase					=distances[u] + self.graph[u][v]

            self.print_solution(__lowercase      )


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'''

from __future__ import annotations

def 				__UpperCamelCase							(	lowercase__						:  list[int | float],					lowercase__						:  int,					lowercase__						:  int ):






     '''simple docstring'''





     if len(lowercase__ ) == 0:
          raise ValueError('find_min() arg is an empty sequence' )
     if (
         left >= len(lowercase__ )
         or left < -len(lowercase__ )
         or right >= len(lowercase__ )
         or right < -len(lowercase__ )
     ):
          raise IndexError('list index out of range' )
     if left == right:
          return nums[left]
     __lowercase					=(left + right) >> 1  # the middle
     __lowercase					=find_min(lowercase__,					lowercase__,					lowercase__ )  # find min in range[left, mid]
     __lowercase					=find_min(lowercase__,					mid + 1,					lowercase__ )  # find min in range[mid + 1, right]

     return left_min if left_min <= right_min else right_min


if __name__ == "__main__":
       import doctest

       doctest.testmod(verbose=True)


