# Discrete Mathematics | Dijkstra's Algorithm and Travelling Salesman Problem MCQs

Discrete Mathematics | Dijkstra's Algorithm and Travelling Salesman Problem MCQs: This section contains multiple-choice questions and answers on Dijkstra's Algorithm and Travelling Salesman Problem in Discrete Mathematics.
Submitted by Anushree Goswami, on October 28, 2022

1. The ____ paths from the source are already known for a set of vertices?

1. Shortest
2. Longest
3. Average
4. Medium

Explanation:

The shortest paths from the source are already known for a set of vertices.

2. Graphs are represented by cost adjacency matrices, where cost represents edge ____?

1. Vertex
2. Point
3. Weight
4. None

Explanation:

Graphs are represented by cost adjacency matrices, where cost represents edge weight.

3. The diagonal values of the graph's cost adjacency matrix are all ____?

1. Zero
2. One
3. Five
4. Infinite

Explanation:

The diagonal values of the graph's cost adjacency matrix are all zero.

4. Vertex Vs is represented by __ if no path exists between it and another vertex Vi?

1. ∞+
2. -∞
3. +∞
4. ∞-

Explanation:

Vertex Vs is represented by +∞ if no path exists between it and another vertex Vi.

5. All weights have been assumed ____ in this algorithm?

1. Real
2. Negative
3. Whole
4. Positive

Explanation:

All weights have been assumed positive in this algorithm.

6. Step-by-step process to get the shortest path from the source vertex to all the vertices is -?

1. Sets have no vertex at the beginning. In S, include the source vertex Vs.
2. You need to determine all the paths from Vs to all the other vertices without passing through any other vertices.
3. Find the shortest paths through the nearest vertex in S to all the other vertices and update the values accordingly.
4. Graphs with n vertices should be repeated until all n-1 vertices are excluded from S.

Select the order in which the process takes place?

1. B > C > D > A
2. A > B > C > D
3. D > C > B > A
4. A > B > D > C

Answer: B) A > B > C > D

Explanation:

Step-by-step process to get the shortest path from the source vertex to all the vertices is-

1. Sets have no vertex at the beginning. In S, include the source vertex Vs.
2. You need to determine all the paths from Vs to all the other vertices without passing through any other vertices.
3. Find the shortest paths through the nearest vertex in S to all the other vertices and update the values accordingly.
4. Graphs with n vertices should be repeated until all n-1 vertices are excluded from S.

7. The Nearest Neighbour Method consist of following steps -?

1. Form the circuit by joining the starting vertex with the last vertex added by an edge.
2. A path of one edge is formed by selecting an arbitrary vertex and finding the vertex nearest to it.
3. A vertex that has been added to the path is denoted by v. Select the closest vertex to v from the list of vertices that are not part of the path, then add the edge connecting this vertex to the path. In this step, repeat the process until the path includes all the vertices of graph G.

Select the correct order in which process should take place -

1. A > B > C
2. B > A > C
3. B > C > A
4. C > A > B

Answer: C) B > C > A

Explanation:

The Nearest Neighbour Method consist of following steps in the given order -

1. A path of one edge is formed by selecting an arbitrary vertex and finding the vertex nearest to it.
2. A vertex that has been added to the path is denoted by v. Select the closest vertex to v from the list of vertices that are not part of the path, then add the edge connecting this vertex to the path. In this step, repeat the process until the path includes all the vertices of graph G.
3. Form the circuit by joining the starting vertex with the last vertex added by an edge.

👇 More MCQs (Category-Wise) 👇

Web Technologies MCQs

Computer Science Subjects MCQs

Databases MCQs

Programming MCQs

Testing Software MCQs

Digital Marketing Subjects MCQs

Cloud Computing Softwares MCQs

AI/ML Subjects MCQs

Engineering Subjects MCQs

Office Related Programs MCQs

Commerce MCQs

Graphic Design Softwares MCQs

General Knowledge (GK) MCQs

Class-wise MCQs

Others