Shortest Path Length (SPL): given a directed graph tt = (V, A), two nodes s, t V , and a length function A : A R+
Consider the following problem:
Shortest Path Length (SPL): given a directed graph tt = (V, A), two nodes s, t V , and a length function A : A R+, find the length of a shortest s–t path.Python code代写
In this coursework, you are asked to write a Python code which implements two variants of Dijkstra’s algorithm for the solution of SPL, run your code to produce data on how the two variants behave in terms of computing time as the size of the graph increases, analyze this data in Excel, and, finally, write up your findings in LaTeX. The LaTeX report is conceived to be similar to a research paper, albeit in a smaller scale.
Write a Python script dijkstra.py containing two functions, dijkstra1() and dijkstra2(), capable of computing the length of a shortest path between the first node of the graph (0) and a second node other_node supplied as input.
Note that, in this activity, we are only interested in the length of a shortest path, rather than in which arcs it contains. The functions should have two inputs: the successors list of the graph, successors, and the destination node other_node.
Assume that successors is implemented as a list of dictionaries where, for all i in V, successors[i] is a dictionary whose keys are the indices of the nodes adjacent to node i and whose values are the lengths of the arcs from i to such nodes.
The function dijkstra1() should contain an implementation of Dijkstra’s algo- rithm in the version seen in the lectures (which solves the “Single Source Shortest Path” problem by computing the shortest path length between 0 and each other node in the graph), modified to return, at the very end of the algorithm, the length of a shortest path between s=0 and t=other_node.
The function dijkstra2() should contain a modified implementation which, after the destination node other_node has been reached, halts the execution of the algorithm (this is correct; do you see why?). Its return value should be the same as dijkstra1().
Comparing the practical efficiency of these two versions of the algorithm is the main aim of this activity.