Answer the following in context of graph algorithms: $(2+4+4=10)$

$($a$)$ Write the Dijkstra's Greedy Criterion for calculating single$-$source shortest paths.

$($b$)$ What is the running time of the straightforward implementation of Dijkstra's algorithm without any special data

structure? Give a step$-$wise implementation of the Dijkstra's algorithm using appropriate data structure$($s$)$ that

runs in $O((m+n)logn)$ running time. Here, $m$ is the number of edges and $n$ the number of vertices in the graph.

Also analyze and show how your implementation features this running time.

$($c$)$ Apply the Bellman$-$Ford Algorithm to find shortest paths from source vertex S to every other vertex in the

following weighted directed graph:

Answer the following in context of complexity classes $P,NP,NP-$Complete, and NP$-$Hard: $(3+3+4=10)$

$($a$)$ What do you mean by a decision problem? State the optimization and decision version of the Travelling

Salesperson Problem $($TSP$).$

$($b$)$ Given a set E of problems, define the set E$-$complete. Also, give the steps through which a problem can be

proven E$-$complete.

$($c$)$ The problem of finding a Hamiltonian Cycle is a known NP$-$Complete problem. Prove by reduction that

Hamiltonian Path is also NP$-$Complete. Clearly explain your reduction with the help of an example.

Answer the following in context of Graph Algorithms: $(2+4+4=10)$

$($a$)$ State the key difference between the Greedy Criterion of Prim's Algorithm and that of the Kruskal's Algorithm.

$($b$)$ The state of an operating system is depicted using a Resource Allocation Graph $($RAG$).$ The RAG stores the

complete information about all the processes which are holding some resources or waiting for some resources.$($c$)$ Apply the Bellman$-$Ford Algorithm to find shortest paths from source vertex S to every other vertex in the

following weighted directed graph: