'''simple docstring'''


from __future__ import annotations






class 	__SCREAMING_SNAKE_CASE		:







  '''simple docstring'''






  def __init__(					self ,						snake_case_		):




       '''simple docstring'''

       UpperCAmelCase_				:  Optional[int]  = vertices
       UpperCAmelCase_				:  Optional[int]  = [[0] * vertices for _ in range(snake_case_		)]


  def _UpperCamelCase	(					self ,						snake_case_		):




       '''simple docstring'''

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


  def _UpperCamelCase	(					self ,						snake_case_ ,						snake_case_		):




       '''simple docstring'''

       UpperCAmelCase_				:  str  = 1E7
       UpperCAmelCase_				:  Tuple  = 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_				:  Optional[Any]  = distances_from_source[vertex]
                 UpperCAmelCase_				:  str  = vertex
       return min_index






  def _UpperCamelCase	(					self ,						snake_case_		):




       '''simple docstring'''

       UpperCAmelCase_				:  int  = [int(1E7		)] * self.vertices  # distances from the source
       UpperCAmelCase_				:  Dict  = 0
       UpperCAmelCase_				:  Tuple  = [False] * self.vertices

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

       self.print_solution(snake_case_		)


if __name__ == "__main__":
 snake_case__	:     str      =    Graph(9)
 snake_case__	:     Optional[Any]      =    [
     [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)









from math import pi



def   UpperCamelCase(   lowercase_				)      ->							float:





  '''simple docstring'''





  return degree / (180 / pi)


if __name__ == "__main__":
    from doctest import testmod

    testmod()