Four claims are listed below. If an associated claim is true, prove it$.$ If you think it is false: either disprove it or

give a counter example.

A$)$ Shortest path problem is an NP$-$Hard problem.

B$)$ Travelling Salesman Problem can be solved in polynomial time with an enumeration $($or exhaustive$)$

algorithm.

C$)$ Dijkstra's Algorithm guarantees an optimal solution for any given graph with negative edges.

D$)$ Nearest Neighborhood Algorithm is an exact algorithm to solve TSP$.$

Find the shortest path from source vertex to all other vertices using Dijkstra's algorithm.