Home » MCQs » Discrete Mathematics MCQs

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

Answer: A) Shortest

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

Answer: C) Weight

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

Answer: D) 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. ∞-

Answer: C) +∞

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

Answer: D) 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.

---

---