from termcolor import colored, cprint



graf = {
   "a":{
      'b':2,
      'h':1,
      'i':8,
      },
   "b":{
      'a':2,
      'c':1,
      'i':6,
   },
   'c':{
      'b':1,
      'i':5,
      'j':3,
      'k':9,
      'd':2,
   },
   'd':{
      'c':2,
      'k':7,
      'e':9,
   },
   'e':{
      'd':9,
      'k':2,
      'f':4,
   },
   'f':{
      'e':4,
      'g':1,
      'k':1,
   },
   'g':{
      'f':1,
      'j':4,
      'h':9,
      'i':2,
      'k':3,
   },
   'h':{
      'g':9,
      'a':1,
      'i':7,
   },
   'i':{
      'a':8,
      'b':6,
      'c':5,
      'g':2,
      'h':7,
      'j':1,
   },
   'j':{
      'i':1,
      'c':3,
      'k':6,
      'g':4,
   },
   'k':{
      'j':6,
      'd':7,
      'f':1,
      'e':2,
      'g':3,
      'c':9,
   }
}


def dijkstra(graph, start, goal):
   predecessor = {}
   unseenNodes = graph
   infinity = float('inf')
   path = []
   shortest_distance = {node: infinity for node in unseenNodes}
   shortest_distance[start] = 0
   odwiedzone = []

   while unseenNodes:
      minNode = None
      for node in unseenNodes:
         if minNode is None:
               minNode = node
         elif shortest_distance[node] < shortest_distance[minNode]:
               minNode = node

      for childNode, weight in graph[minNode].items():
         if weight + shortest_distance[minNode] < shortest_distance[childNode]:
               shortest_distance[childNode] = weight + shortest_distance[minNode]
               predecessor[childNode] = minNode


      if minNode != start:
         print(f"Wybieram: {colored( minNode, 'green')} ---- ",end='')
         for key in shortest_distance.keys(): # jeśli będzie więcej niż dwucyfrowe liczby to trzeba zmienić 3 na 4 itp nie chciało mi się tego robić już
            ile_znakow = len(str(shortest_distance[key]))
            ile_znakow = 3 - ile_znakow # o tu
            if shortest_distance[key] == float('inf'):
               print(f"{key}:{colored( shortest_distance[key],'red') } {ile_znakow*' '} ", end='')
            elif key in odwiedzone:
               print(f"{key}:{colored('-','red') } {2*' '} ", end='')
            else:
               print(f"{key}:{colored( shortest_distance[key],'green') } {ile_znakow*' '} ", end='')
         print('')

      odwiedzone.append(minNode)
      unseenNodes.pop(minNode)


   cprint((len(odwiedzone)*'   ') + "Tabelka została zakończona!\n", 'red', attrs=['bold'])
   currentNode = goal
   while currentNode != start:
      try:
         path.insert(0,currentNode)
         currentNode = predecessor[currentNode]
      except KeyError:
         print('Path not reachable')
         break
   path.insert(0,start)
   if shortest_distance[goal] != infinity:
      print('Koszt ścieżki: ' + colored( str(shortest_distance[goal]), 'cyan'))
      print('Ścieżka to: ', end='')
      for i in path:
         if i != path[-1]:
            print(colored(i, 'magenta') + ' => ', end='')
         else:
            print(colored(i, 'magenta'), end='')

dijkstra(graf, 'a', 'e')