## Shortest-Path

 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. A SDT B SBDT C SACDT D SACET
Algorithms        Shortest-Path       Gate 2012
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.
 Question 2
Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one Q. Finds whether any negative weighted cycle is reachable from the source.
 A P Only B Q Only C Both P and Q D Neither P nor Q
Algorithms        Shortest-Path       2009
Question 2 Explanation:
Bellman-Ford 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.
--A greedy algorithm
--Works when weights are all non-negative
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 |V|-1 edges
---A dynamic programming algorithm
Note: Dijkastra is faster than Bellman-Ford
 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 A only vertex a B only vertices a, e, f, g, h C only vertices a, b, c, d D all the vertices
Algorithms       Shortest-Path       Gate-2008
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.
A-B ⇒ 1
A-C⇒ 1+2=3
A-E⇒ 1-3 =-2
A-F⇒ 1 -3 +2 =0
A-G⇒ 1 -3 +2 +3 =3
A-C ⇒1 +2 =3
A-H⇒ 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:
 A O(|V|2) B O(|E|+|V|log|V|) C O(|V|log|V|) D O((|E|+|V|)log|V|)
Algorithms        Shortest-Path       Gate-2005
Question 4 Explanation:
O(ElogV) equals to O((|E|+|V|)log|V|)
In worst case graph will be a complete graph i.e total edges = v(v-1)/2 where v is no. of vertices.
E<=v2
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(v2 + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
 Question 5
 A P, Q, R, S, T, U B P, Q, R, U, S, T C P, Q, R, U, T, S D P, Q, T, R, U, S
Algorithms        Shortest-Path       Gate-2004
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 single-source 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?
 A The number of edges in the shortest paths from v1 to all vertices of G B G1 is connected C V1 forms a clique in G D G1 is a tree
Algorithms        Shortest-Path       Gate-2003
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?
 A Dynamic programming B Backtracking C Greedy D Divide and Conquer
Algorithms        Shortest-Path       Gate-1998
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.