[Python 3] You will implement two algorithms to find the shortest path in a graph.

def dijkstra(G, start_node): Takes an Adjacency Matrix G and the index of the starting node start_node. Returns the distance array.

def floyd(G): Takes an Adjacency Matrix G and returns the distance matrix

The graph you are working on will be give in a file with the following format. These graphs are directed, if an edge can be used in both directions, it must be given twice.

Line 1: The number of Nodes in the Graph Lines 2-EOF: Every other line in the file contains an edge First Value is the FROM node Second Value is the TO node Third Value is the weight of the edge Note: You should store the weights as floats.

The program will have a text interface. First ask for the file name of the graph to work with. Then implement 4 text commands.

dijkstra x - Runs Dijkstra starting at node X. X must be an integer

floyd - Runs Floyd's algorithm

help - prints this menu

exit - Exits the program

You must implement this using only standard python3 libraries. You may not use any outside libraries. For example, open source graph libraries. You may not include any other python files. You may use either an adjacency matrix or adjacency list.

Example Run 1:

File containing graph: input1.txt Possible Commands are: dijkstra x - Runs Dijkstra starting at node X. X must be an integer floyd - Runs Floyd's algorithm help - prints this menu exit or ctrl-D - Exits the program Enter command: help Possible Commands are: dijkstra x - Runs Dijkstra starting at node X. X must be an integer floyd - Runs Floyd's algorithm help - prints this menu exit or ctrl-D - Exits the program Enter command: dijkstra 0 [0.0, 1.0, 3.0, 5.0, 7.0] Enter command: exit Bye ---------------- Example Run 2:

File containing graph: input1.txt Possible Commands are: dijkstra x - Runs Dijkstra starting at node X. X must be an integer floyd - Runs Floyd's algorithm help - prints this menu exit or ctrl-D - Exits the program Enter command: dijkstra 0 [0.0, 1.0, 3.0, 5.0, 7.0] Enter command: dijkstra 1 [inf, 0.0, 2.0, 4.0, 6.0] Enter command: dijkstra 2 [inf, 3.0, 0.0, 2.0, 4.0] Enter command: dijkstra 3 [inf, 1.0, 3.0, 0.0, 7.0] Enter command: dijkstra 4 [inf, 6.0, 8.0, 5.0, 0.0] Enter command: exit Bye ---------------- Example Run 3:

File containing graph: input1.txt Possible Commands are: dijkstra x - Runs Dijkstra starting at node X. X must be an integer floyd - Runs Floyd's algorithm help - prints this menu exit or ctrl-D - Exits the program Enter command: floyd [0.0, 1.0, 3.0, 5.0, 7.0] [inf, 0.0, 2.0, 4.0, 6.0] [inf, 3.0, 0.0, 2.0, 4.0] [inf, 1.0, 3.0, 0.0, 7.0] [inf, 6.0, 8.0, 5.0, 0.0] Enter command: exit Bye ---------------- Example Run 4:

File containing graph: input2.txt Possible Commands are: dijkstra x - Runs Dijkstra starting at node X. X must be an integer floyd - Runs Floyd's algorithm help - prints this menu exit or ctrl-D - Exits the program Enter command: dijkstra 0 [0.0, 3.0, 4.0, 4.0, inf, 4.0] Enter command: dijkstra 1 [inf, 0.0, 1.0, 3.0, inf, 1.0] Enter command: dijkstra 2 [inf, 5.0, 0.0, 2.0, inf, 6.0] Enter command: dijkstra 3 [inf, 3.0, 4.0, 0.0, inf, 4.0] Enter command: dijkstra 4 [inf, 6.0, 7.0, 3.0, 0.0, 2.0] Enter command: dijkstra 5 [inf, 5.0, 6.0, 2.0, inf, 0.0] Enter command: floyd [0.0, 3.0, 4.0, 4.0, inf, 4.0] [inf, 0.0, 1.0, 3.0, inf, 1.0] [inf, 5.0, 0.0, 2.0, inf, 6.0] [inf, 3.0, 4.0, 0.0, inf, 4.0] [inf, 6.0, 7.0, 3.0, 0.0, 2.0] [inf, 5.0, 6.0, 2.0, inf, 0.0] Enter command: exit Bye ----------------

The content of the test files is given below.

input1.txt

5 0 1 1 1 2 2 2 3 2 2 4 4 3 1 1 3 2 3 4 3 5

-----------

input2.txt

6 0 1 3 0 3 4 0 5 5 1 5 1 1 2 1 2 3 2 3 1 3 4 3 3 4 5 2 5 3 2

-----------

input3.txt

8 4 5 35 5 4 35 4 7 37 5 7 28 7 5 28 5 1 32 0 4 38 0 2 26 7 3 39 1 3 29 2 7 34 6 2 40 3 6 52 6 0 58 6 4 93