Guest User

Untitled

a guest
Nov 22nd, 2020
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from termcolor import colored, cprint
  2.  
  3.  
  4.  
  5. graf = {
  6.    "a":{
  7.       'b':2,
  8.       'h':1,
  9.       'i':8,
  10.       },
  11.    "b":{
  12.       'a':2,
  13.       'c':1,
  14.       'i':6,
  15.    },
  16.    'c':{
  17.       'b':1,
  18.       'i':5,
  19.       'j':3,
  20.       'k':9,
  21.       'd':2,
  22.    },
  23.    'd':{
  24.       'c':2,
  25.       'k':7,
  26.       'e':9,
  27.    },
  28.    'e':{
  29.       'd':9,
  30.       'k':2,
  31.       'f':4,
  32.    },
  33.    'f':{
  34.       'e':4,
  35.       'g':1,
  36.       'k':1,
  37.    },
  38.    'g':{
  39.       'f':1,
  40.       'j':4,
  41.       'h':9,
  42.       'i':2,
  43.       'k':3,
  44.    },
  45.    'h':{
  46.       'g':9,
  47.       'a':1,
  48.       'i':7,
  49.    },
  50.    'i':{
  51.       'a':8,
  52.       'b':6,
  53.       'c':5,
  54.       'g':2,
  55.       'h':7,
  56.       'j':1,
  57.    },
  58.    'j':{
  59.       'i':1,
  60.       'c':3,
  61.       'k':6,
  62.       'g':4,
  63.    },
  64.    'k':{
  65.       'j':6,
  66.       'd':7,
  67.       'f':1,
  68.       'e':2,
  69.       'g':3,
  70.       'c':9,
  71.    }
  72. }
  73.    
  74.  
  75. def dijkstra(graph, start, goal):
  76.    predecessor = {}
  77.    unseenNodes = graph
  78.    infinity = float('inf')
  79.    path = []
  80.    shortest_distance = {node: infinity for node in unseenNodes}
  81.    shortest_distance[start] = 0
  82.    odwiedzone = []
  83.  
  84.    while unseenNodes:
  85.       minNode = None
  86.       for node in unseenNodes:
  87.          if minNode is None:
  88.                minNode = node
  89.          elif shortest_distance[node] < shortest_distance[minNode]:
  90.                minNode = node
  91.  
  92.       for childNode, weight in graph[minNode].items():
  93.          if weight + shortest_distance[minNode] < shortest_distance[childNode]:
  94.                shortest_distance[childNode] = weight + shortest_distance[minNode]
  95.                predecessor[childNode] = minNode
  96.  
  97.    
  98.       if minNode != start:
  99.          print(f"Wybieram: {colored( minNode, 'green')} ---- ",end='')
  100.          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ż
  101.             ile_znakow = len(str(shortest_distance[key]))
  102.             ile_znakow = 3 - ile_znakow # o tu
  103.             if shortest_distance[key] == float('inf'):
  104.                print(f"{key}:{colored( shortest_distance[key],'red') } {ile_znakow*' '} ", end='')
  105.             elif key in odwiedzone:
  106.                print(f"{key}:{colored('-','red') } {2*' '} ", end='')
  107.             else:
  108.                print(f"{key}:{colored( shortest_distance[key],'green') } {ile_znakow*' '} ", end='')
  109.          print('')
  110.          
  111.       odwiedzone.append(minNode)
  112.       unseenNodes.pop(minNode)
  113.    
  114.    
  115.    cprint((len(odwiedzone)*'   ') + "Tabelka została zakończona!\n", 'red', attrs=['bold'])
  116.    currentNode = goal
  117.    while currentNode != start:
  118.       try:
  119.          path.insert(0,currentNode)
  120.          currentNode = predecessor[currentNode]
  121.       except KeyError:
  122.          print('Path not reachable')
  123.          break
  124.    path.insert(0,start)
  125.    if shortest_distance[goal] != infinity:
  126.       print('Koszt ścieżki: ' + colored( str(shortest_distance[goal]), 'cyan'))
  127.       print('Ścieżka to: ', end='')
  128.       for i in path:
  129.          if i != path[-1]:
  130.             print(colored(i, 'magenta') + ' => ', end='')
  131.          else:
  132.             print(colored(i, 'magenta'), end='')
  133.  
  134. dijkstra(graf, 'a', 'e')
RAW Paste Data