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 Dijkstra'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 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.
P Only | |
Q Only | |
Both P and Q | |
Neither P nor Q |
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.
More Info: The Dijkstra'a algorithm:
--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
More Info: The Dijkstra'a algorithm:
--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
There are 2 questions to complete.
