help with the bolded question at the end.

Q4(a)(iv) (2 Marks)

Use Dijsktra's algorithm to compute a shortest path from despatch to each zone. Draw the resulting tree.

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)

warehouse.draw()

# Write your code here

def dijkstra(graph, source, dest): # Initialize distances and previous nodes distances = {node: float('inf') for node in graph.nodes} distances[source] = 0 previous = {node: None for node in graph.nodes} # Initialize priority queue queue = PriorityQueue() queue.put(source, 0) # Loop until the priority queue is empty while not queue.empty(): # Get the node with the smallest distance node = queue.get() # Update distances and previous nodes for neighbors for neighbor in graph.neighbors(node): new_distance = distances[node] + graph.weight(node, neighbor) if new_distance < distances[neighbor]: distances[neighbor] = new_distance previous[neighbor] = node queue.put(neighbor, new_distance) # Return the shortest path return get_path(previous, source, dest)

def get_path(previous, source, dest): # Initialize the path path = [] # Iterate through the previous nodes until the source is reached node = dest while node is not None: path.append(node) node = previous[node] # Return the reversed path return path[::-1]

Q4(a)(v) (10 marks)

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).)

help with the following bolded question.

Analyse the worst-case complexity of this algorithm for a connected weighted digraph warehouse with n nodes and e edges, explaining the worst-case complexity of each step as well as the overall complexity. You should assume that the graph is represented as adjacency sets of out-neighbours.