ER-Model
May 20, 2024Network-Security
May 20, 2024Algorithms
| Question 25 |
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 25 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.
Correct Answer: D
Question 25 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.