from collections import defaultdict import heapq import networkx as nx import matplotlib.pyplot as plt class WeightedDiGraph: def __init__(self): self.graph = defaultdict(list) def add_node(self, vertex): self.graph[vertex] = [] def add_edge(self, start, end, weight): self.graph[start].append((end, weight)) def dijkstra(graph, start): # initialize distances with infinity distances = {vertex: float('infinity') for vertex in graph} # the distance to the start vertex is 0 distances[start] = 0 # create a priority queue pq = [(0, start)] # keep track of the edges used to reach each vertex edges = {} while pq: # get the vertex with the smallest distance so far (distance, current_vertex) = heapq.heappop(pq) # skip this vertex if we have already found a shorter path if distance > distances[current_vertex]: continue # update the distances of the neighbors of the current vertex for (neighbor, weight) in graph[current_vertex]: distance_to_neighbor = distance + weight if distance_to_neighbor < distances[neighbor]: distances[neighbor] = distance_to_neighbor # record the edge used to reach this neighbor edges[neighbor] = (current_vertex, neighbor, weight) heapq.heappush(pq, (distance_to_neighbor, neighbor)) return distances, edges # Use Dijsktra's algorithm to compute a shortest path from despatch to each zone. warehouse = WeightedDiGraph() warehouse.add_node('despatch') warehouse.add_node('A') warehouse.add_node('D') warehouse.add_node('P') warehouse.add_node('S') warehouse.add_node('U') warehouse.add_node('Y') warehouse.add_node('Z') warehouse.add_edge('despatch', 'U',30) warehouse.add_edge('U', 'despatch',30) warehouse.add_edge('despatch', 'A',10) warehouse.add_edge('A', 'despatch',10) warehouse.add_edge('despatch', 'D',5) warehouse.add_edge('D', 'despatch',5) warehouse.add_edge('despatch','Z',16) warehouse.add_edge('Z', 'despatch',16) warehouse.add_edge('A', 'U',15) warehouse.add_edge('U', 'A',15) warehouse.add_edge('A', 'P',10) warehouse.add_edge('P', 'A',10) warehouse.add_edge('P', 'S',12) warehouse.add_edge('S', 'P',12) warehouse.add_edge('D', 'Z',8) warehouse.add_edge('Z', 'D',8) warehouse.add_edge('P', 'D',15) warehouse.add_edge('D', 'P',15) warehouse.add_edge('P', 'Y',8) warehouse.add_edge('Y','P',8) warehouse.add_edge('Y','S',12) warehouse.add_edge('S', 'Y',12) warehouse.add_edge('Y', 'Z',15) warehouse.add_edge('Z', 'Y',15) distances, edges = dijkstra(warehouse.graph, 'despatch') G = nx.Graph() G = nx.DiGraph() # Add nodes to the graph for node in warehouse.graph: G.add_node(node) # Add edges to the graph for node in warehouse.graph: for neighbor, weight in warehouse.graph[node]: if distances[neighbor] == distances[node] + weight: G.add_edge(node, neighbor, weight=weight) # Draw the graph pos = {'despatch': (0,0),'A': (0, 1), 'U': (0, 2), 'P': (1, 1), 'S': (2, 1), 'D': (1, 0), 'Y':(3,0), 'Z': (2,0)} nx.draw_networkx_nodes(G, pos) nx.draw_networkx_edges(G, pos,width=1, arrowsize=10) nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): d['weight'] for u, v, d in G.edges(data=True)}) nx.draw_networkx_labels(G, pos) plt.show()

Q4(a)(v) Here is a definition of a function that, given a connected weighted digraph, finds the shortest path from a given start node to a given end node.

Function: shortest path between nodes

Inputs: warehouse, a weighted digraph; start, a node; end, a node

Preconditions: start and end are different nodes in warehouse; warehouse is connected

Output: path, a sequence of nodes

Postconditions: path is the shortest path from start to end in warehouse

Here is a description of an algorithm that solves the shortest path between nodes problem.

Use Dijkstra's algorithm to construct a tree of shortest paths from start to every other node of warehouse. Let path be the sequence [end]. In the tree, starting with end visit the in-neighbour of the node, then the in-neighbour of that node, and so on, until getting to start, appending each node to path. Reverse the sequence path using reverse_in_place() as defined in Exercise 4.7.7 answer. (Note: The code for reverse_in_place() is reproduced in Q4(a)(vi).)

Implement this shortest path between nodes algorithm as a function in Python. Include a docstring. We have provided the reverse_in_place() code as given in the answer to Exercise 4.7.7. Make sure that your function inputs are in the order warehouse, start, end.

Test your implementation by running the test code given below. If any tests fail, then debug your implementation and run the test code again. You can repeat this iterative process as many times as you want. If there are any tests that fail and you are unable to identify the problem, you may add explanatory comments below the test code.

%run -i m269_util # The reverse_in_place code appears in Exercise 4.7.7 answer def reverse_in_place(values: list) -> None: """Reverse the order of the values.

Postconditions: post-values = [pre-values[len(pre-values) - 1], ..., pre-values[1], pre-values[0]] """ left_index = 0 right_index = len(values) - 1 while left_index < right_index: left_item = values[left_index] values[left_index] = values[right_index] values[right_index] = left_item left_index = left_index + 1 right_index = right_index - 1

# Write your function code here

# Test code shortest_path_tests = [ # case, warehouse, start, end, shortest path ('neighbouring zones', warehouse, 'S', 'Y', ['S','Y']), ('zone neighbouring despatch', warehouse, 'despatch', 'D', ['despatch','D']), ('zone neighbouring despatch shortest path not direct', warehouse, 'despatch','Z', ['despatch','D','Z']), ('distant zones', warehouse, 'U', 'D', ['U','A','despatch','D']), ('distant zones opposite direction', warehouse, 'D', 'U', ['D','despatch','A','U']), ('two different shortest paths, choice depends on dijkstra', warehouse, 'Z', 'P', ['Z','D','P']), ] test(shortest_path_between_nodes, shortest_path_tests) # Add any explanatory comments here