Single$-$Source Shortest Paths

Description: You are to implement the following algorithms: DAG SP algorithm,

Dijkstra$$s algorithm, and the Bellman$-$Ford algorithm for single$-$source shortest paths

based on $($i$)$ whether or not you detect a cycle and $($ii$)$ whether or not you detect any

negative edge weights. If there is no cycle, then run the DAG SP algorithm. If there is

a cycle but no negative edges, then run Dijkstra. Otherwise, run Bellman$-$Ford. You

are to run your program on meaningful sets of input graphs across varying types

$($DAG$,$ only positive weights, general weights and cycles$),$ varying sizes $($n$),$ and

varying edge densities $($m$/$n$).$ Based on your experiments, you are to analyze the

comparative time complexities of the different SPT algorithms across the different

sizes and edge densities for their given type. Your experimental analyses should be

compared to the known theoretical time complexities. And, all of your analyses

should be contained in a detailed report with plots, which you submit along with your

code and input graphs for this project.

I$/$O Specifications for the User: These specifications pertain to the functionality of your

project when a user is running your code. You will prompt the user for the graph input file of

the weighted adjacency list representation and format consistent with the sample files. You

will also prompt the user for the source node. Moreover, continue to prompt the user for the

destination node, allowing the user to select different destination nodes based on the same

source. Regarding your output, which will be to the console:

$$ First state whether or not the graph is a DAG, and if so indicate that you will run $$DAG

SP algorithm$.$ Otherwise, state whether or not the non$-$DAG graph has any negative

edge weights. If the graph is not a DAG and has only positive edges, indicate that you

will run $$Dijkstra$$s algorithm$.$ Otherwise, state that the graph is not a DAG and has

negative weight edges, indicating that you will run $$Bellman$-$Ford algorithm$.$

$$ If a negative weight cycle exists, output this fact to the console and exit.

$$ Otherwise, regardless of the graph type, output both the shortest path from the source to

the destination, and the total length of that path.

$$ Continue to prompt for another destination until the user quits.

Algorithmic Specifications: You must save your input graphs into an adjacency list based

graph structure of your own construction. This is important for time complexity

considerations. You yourself are to implement the following three shortest paths algorithms

as separate methods consistent with the provided zybook, slides, and video lecture:

$$ DAG Shortest$-$Paths algorithm: This algorithm must run in time O$(|$E$|+|$V$|)$ and

involves calls to DFS$,$ which you must also implement as a separate method.

o DFS is used in the checking for cycles separately.

$$ Dijkstra$$s Algorithm: This algorithm must run in time O$(|$E$|$ log $|$V$|)$ and involves a priority

queue $($heap$)$ structure, which you have already implemented and used in Project $1.$ You

are allowed to use either your own implementation of the heap or a built$-$in heap. Whatever

you choose regarding the heap, you must implement Dijkstra$$s algorithm yourself.$$ Bellman$-$Ford Algorithm: Although this algorithm is the most time$-$intensive, taking

O$(|$E$||$V$|)$ time, you may find that it is actually the easiest one to implement. The only extra

data structure required for this is a list of all the edges of your graph.

These specifications of the SPT algorithms pertain to both the user runs and the experiments.

FurtherspecificationsfortheUserRuns:You need to check the graph for the existence of any

cycle in the graph using DFS$,$ and if no cycle is detected $($i$.$e$.$ no back edges$)$ you will run the

topological$-$sort based shortest path algorithm for DAGs taking O$(|$E$|+|$V$|)$ time. If the graph

is not acyclic, but has only positive weight edges, you will run Dijkstra$$s algorithm which

takes O$(|$E$|$ log $|$V$|)$ time. Otherwise, you will run Bellman$-$Ford algorithm $($taking O$(|$E$||$V$|)$

time$).$ If you detect a negative weight cycle in the graph, you will output this fact to the

console and exit. Otherwise, you will keep prompting the user to input a destination node

whose shortest path from the source you will output to the console, including both the nodes

along the shortest path and the overall shortest path cost.

Specifications for the Time Complexity Experiments: In addition to allowing the userfriendly runs as described above, you yourself will also be running your three implemented

shortest$-$paths algorithms in $$batch$$ mode over several generated input graphs for the

purpose of analyzing the actual time complexities of your coded algorithms. We are

separately providing a graph generator source code and the description of the generated

graph adjacency list format in the zipped folder graph$-$generator.zip which you may use to

generate input graphs for your experiments.