ShortestPath
Question 1 
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
SDT  
SBDT  
SACDT  
SACET 
Question 1 Explanation:
They did not ask about shortest paths from S to T but they had asked the shortest path obtained by applying Dijkstra algorithm. If we apply Dijkstra algorithm we got path from S to T 10 only after relaxing edges through E and E will get 6 only after relaxing edges through C and C will get 5 only after relaxing edges through A. So, the shortest path from S to T if we follow Dijkstra algorithm is S,A,C,E,T.
The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.
Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.
So, path is S, A, C, E, T.
Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.
The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.
Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.
So, path is S, A, C, E, T.
Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.
Question 2 
Which of the following statement(s) is / are correct regarding BellmanFord shortest path algorithm?
P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.
P Only  
Q Only
 
Both P and Q
 
Neither P nor Q

Question 2 Explanation:
BellmanFord shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
Question 3 
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
only vertex a  
only vertices a, e, f, g, h
 
only vertices a, b, c, d
 
all the vertices 
Question 3 Explanation:
The single source shortest path algorithm(Dijkstra’s) is not work correctly for negative edge weights and negative weight cycle. But as per the above graph it works correct. It gives from shortest path between ‘a’ vertex to all other vertex. The Dijkstra’s algorithm will follow greedy strategy.
AB ⇒ 1
AC⇒ 1+2=3
AE⇒ 13 =2
AF⇒ 1 3 +2 =0
AG⇒ 1 3 +2 +3 =3
AC ⇒1 +2 =3
AH⇒ 1+2 5 =2
AB ⇒ 1
AC⇒ 1+2=3
AE⇒ 13 =2
AF⇒ 1 3 +2 =0
AG⇒ 1 3 +2 +3 =3
AC ⇒1 +2 =3
AH⇒ 1+2 5 =2
Question 4 
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
O(V^{2})
 
O(E+VlogV)  
O(VlogV)
 
O((E+V)logV)

Question 4 Explanation:
O(ElogV) equals to O((E+V)logV)
In worst case graph will be a complete graph i.e total edges = v(v1)/2 where v is no. of vertices.
E<=v^{2}
Time Complexity of Dijkstra's algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v^{2} + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
In worst case graph will be a complete graph i.e total edges = v(v1)/2 where v is no. of vertices.
E<=v^{2}
Time Complexity of Dijkstra's algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v^{2} + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
Question 5 
P, Q, R, S, T, U
 
P, Q, R, U, S, T
 
P, Q, R, U, T, S
 
P, Q, T, R, U, S

Question 5 Explanation:
P, Q, R, U, S, T
Question 6 
Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows :
A singlesource shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?
The number of edges in the shortest paths from v_{1} to all vertices of G  
G_{1} is connected
 
V_{1} forms a clique in G  
G_{1} is a tree

Question 6 Explanation:
Calculate the minimum weight of the graph by using single source shortest path, if the weight of the graph is 0 then G is Connected, then that is the shortest path. In case the weight of the graph is not 0 then the graph G is disconnected.
Question 7 
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
Dynamic programming  
Backtracking  
Greedy  
Divide and Conquer 
Question 7 Explanation:
In Dynamic programming Floyd Warshall algorithm is used to calculate the all pairs shortest path distance.
There are 7 questions to complete.