akbarbasya26

TB2 algo p13

Dec 1st, 2020
845
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from tkinter import *
  2.  
  3. class program():
  4.  
  5.   def __init__(self):
  6.       graph = {
  7.         'o':{'a':2,'b':5,'c':4},
  8.         'a':{'b':2,'d':7,'f':12},
  9.         'b':{'d':4,'e':3},
  10.         'c':{'b':1,'e':4},
  11.         'd':{'e':1,'t':5},
  12.         'e':{'t':7},
  13.         'f':{'t':3},
  14.         't':{'f':3,'e':7,'d':5}
  15.       }
  16.  
  17.       start = 'o'
  18.       goal = 't'
  19.  
  20.       self.root = Tk()
  21.       self.root.title("Quiz P13")
  22.       self.root.geometry("240x80")
  23.       self.root.resizable(width=False, height=False)
  24.       self.dijkstra(graph,start,goal)
  25.       self.root.mainloop()
  26.  
  27.   def dijkstra(self,graph,start,goal):
  28.       shortest_distance = {}
  29.       track_predecessor = {}
  30.       start = 'o'
  31.       goal = 't'
  32.       unseenNodes = graph
  33.       infinity = 999999
  34.       track_path = []
  35.  
  36.       for node in unseenNodes:
  37.         shortest_distance[node] = infinity
  38.         shortest_distance[start] = 0
  39.  
  40.       while unseenNodes:
  41.        
  42.         min_distance_node = None
  43.        
  44.         for node in unseenNodes:
  45.           if min_distance_node is None:
  46.             min_distance_node = node
  47.           elif shortest_distance[node] < shortest_distance[min_distance_node]:
  48.               min_distance_node = node
  49.  
  50.         path_options = graph[min_distance_node].items()
  51.  
  52.         for child_node, weight in path_options:
  53.  
  54.           if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
  55.             shortest_distance[child_node] = weight + shortest_distance[min_distance_node]
  56.             track_predecessor[child_node] = min_distance_node
  57.  
  58.         unseenNodes.pop(min_distance_node)
  59.  
  60.       currentNode = goal
  61.  
  62.       while currentNode != start:
  63.         try:
  64.           track_path.insert(0, currentNode)
  65.           currentNode = track_predecessor[currentNode]
  66.  
  67.         except KeyError:
  68.           print("Path is not reachable")
  69.           break
  70.  
  71.       track_path.insert(0,start)
  72.  
  73.       if shortest_distance[goal] != infinity:
  74.         frame = LabelFrame(self.root, text=" Akbar Basyarudin - 41519010046 ", bd=8,fg='red', bg="green")
  75.        
  76.         Label(frame, text='Jarak dari O ke T', fg='red', bg='green').place(x=0, y=0)
  77.         self.distance_goal = str(shortest_distance[goal])
  78.         Label(frame, text='Jarak Terpendek       :  ' + self.distance_goal, fg='red', bg='green').place(x=0, y=17)
  79.         self.trackpath = str(track_path)
  80.         Label(frame, text='Jalur yang Optimal  :  ' + self.trackpath, fg='red', bg='green').place(x=0, y=34)
  81.         frame.pack(expand=YES, fill=BOTH)
  82.  
  83. program()
RAW Paste Data