-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijks.py
73 lines (56 loc) · 3.58 KB
/
Dijks.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import tkinter as tk
import sys
class Dijkstra: # Class for Dijkstra's algorithm
def __init__(self):
self.nodes = {} # holds user graph
self.visited_nodes = {} # holds all visited nodes
self.distance_node = {} # hold distance to nodes (visited nodes)
self.start = None # start node
self.end = None # end node
self.shortest_path = [] # nodes in shortest path
# Method sets up distances initially to all nodes
# Undiscovered nodes are set to maxint so they can be updated when
# a shorter path is found.
def setup_distances(self):
for node in self.nodes:
if node == self.start:
self.distance_node[node] = 0
else:
self.distance_node[node] = sys.maxsize
def alternate_path(self, pq_key, pq_dict): # Method to calculate alternate paths
alt_path_value = None
# For each neighbour in currently selected parent node , we must check all possible paths from it
for neighbour in self.nodes[pq_key]:
alt_path_value = self.nodes[pq_key][neighbour] + self.distance_node[pq_key]
# If alt path is of shorter value that the path already exisiting , update values with new one.
if alt_path_value < self.distance_node[neighbour]:
self.distance_node[neighbour] = alt_path_value # new shortest distance to neighbour node is alt path
self.visited_nodes[neighbour] = pq_key # neighbour node has been visited
if alt_path_value < pq_dict[neighbour]: # make changes to priority queue for new shorter length path
pq_dict[neighbour] = alt_path_value
def create_path(self): # Method to work out shortest path
route_node = self.end
found_start_node = False # bool to check if start node has been found
while not found_start_node: # Tracing back from end node until start node found
if self.visited_nodes[route_node] == self.start:
self.shortest_path.append(route_node) # adds penultimate node to sp
self.shortest_path.append(self.visited_nodes[route_node]) # adds first node (start node)
found_start_node = True
else:
self.shortest_path.append(route_node)
route_node = self.visited_nodes[route_node]
self.shortest_path = self.shortest_path[::-1] # Reverse list as end node was 'start' node when tracing back
def calc_shortest_path(self): # Method that calculates shortest path through graph
import Priorityqueue as PQ # Priority queue module imported
self.setup_distances() # calling member method
pq = PQ.PriorityQueue() # Priority queue class called using composition
pq_dict = pq.setup_pq(self.nodes, self.start, self.end) # holds dictionary that is priority queue
while len(pq_dict) != 0: # When pq is empty all nodes have been checked so algorithm has completed
pq_key = pq.lowest_value() # holds key of element that had highest priority
self.alternate_path(pq_key, pq_dict) # alt path method called
if self.start == self.end: # If start and end node are same then distance is zero and algorithm ends
tk.messagebox.showinfo('title', "start and end vertex same so distance is zero")
break
if pq_key == self.end: # If end node has been found algorithm can end as shortest path to it was found
self.create_path()
break