Bissoy.com
Doctors Medicines MCQs Q&A

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.

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. Correct Answer SACET

The correct answer is “option 4”.

CONCEPT:

Dijkstra’s algorithm is an algorithm used for finding the shortest paths between nodes or vertices in a graph.

 This algorithm is basically used to find the shortest path from a starting node to a target node in a weighted graph.

This algorithm creates a tree of the shortest path from a vertex to other nodes in the graph.

This algorithm assigns initial distance values & will try to improve step by step.

Dijkstra’s algorithm works as follows:

1. It initializes distances according to the algorithm.

2. Pick a node and calculate the distance to adjacent nodes.

3. Pick the next node with the smallest distance & repeat distance calculations.

4. Find the result of the shortest-path tree.

CALCULATION:

 

S

A

C

E

G

D

B

F

T

 

S

0

∞

∞

∞

∞

∞

∞

∞

∞

 

SB

0

4

∞

∞

∞

7

3

∞

∞

SELECT B

SBA

0

4

∞

∞

∞

7

3

∞

∞

SELECT A

SBAC

0

4

5

∞

∞

7

3

∞

∞

SELECT C

SBACE

0

4

5

6

∞

7

3

∞

∞

SELECT E

SBACED

0

4

5

6

8

7

3

∞

10

SELECT D

SBACEDT

0

4

5

6

8

7

3

12

10

SELECT T

The shortest-path tree is:

[ alt="F1 Raju S 19.5.21 Pallavi D10" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju%20S_19.5.21_Pallavi_D10.png" style="width: 383px; height: 145px;">

Hence, the shortest path from S to T is S → A → C → E → T. 

Related Questions

Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below. The objective is to find the shortest-cost path from the router R to routers P and Q. Assume that R does not initially know the shortest routes to P and Q. Assume that R has three neighbouring routers denoted as X, Y, and Z. During one iteration, R measures its distance to its neighbours X, Y, and Z as 3, 2, and 5, respectively. Router R gets routing vectors from its neighbours that indicate that the distance to router P from routers X, Y, and Z are 7, 6, and 5, respectively. The routing vector also indicates that the distance to router Q from routers X, Y, and Z are 4, 6, and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of R, after updation during this iteration ? 
Consider a network with nodes 1, 2, 3, 4, 5 and 6. The nodes are connected with directed arcs as shown in the table below. The respective costs (in INR) incurred while traversing the directed arcs are also mentioned. Directed arcs  1 → 2 1 → 3 2 → 4 2 → 5 3 → 2 3 → 4 3 → 5 4 → 5 4 → 6 5 → 6 Cost (in INR) 3 9 3 2 2 4 8 7 2 2 The second shortest path from node 1 to node 6 (i.e. the path that has the second least total cost and does not use any part of the shortest path) has a total cost (in INR) of
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
Given below are some famous algorithms and some algorithm design paradigms Algorithms Design Paradigm  1. Dijkstra's shortest path algorithms  (a) Greedy design  2. Floyd-Warshall's all-pair-shortest path algorithms  (b) Divide and conquer  3. Kruskal's minimum spanning tree algorithm  (c) Dynamic programming  4. Merge Sort algorithm     Which of the following correspondence is correct?
Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?