﻿

# 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