An educational institution has study centers distributed across India in the fol

Question

An educational institution has study centers distributed across India in the following locations, Bangalore, Chennai, Hyderabad, Kolkata, Delhi and Pune. The distance between these cities are given below, (B,C=5),(B,H=6),(B,P=8),(C,P=2),(C,D=7),(P,D=7),(P,K=3),(H,K=2) and (K,D=5).

(Hint: (B, C=5) means Bangalore to Chennai the distance is 5).

You have to the following;

A) Construct a Graph and Identify the graph is directed or undirected.

B) Identify the source vertex.

C) The manager wants to send some information to all the regions from source, so identify the shortest path from source to other centers by using single source shortest path algorithm.

Explanation / Answer

A) The current problem can be analysed as follows:

Vertices={B,C,H,K,D,P}

Weight-> Bangalore->Chennai=5

Weight-> Bangalore->Hyderabad=5

Following the same pattern, this graph can be represented as:

This is a directed graph.

B. A source vertex is a vertex that has no vertices incident on it. Therefore, in the above graph, B is the source vertex.

C. Steps in solving single shortest path algorithm:

1) Assigning an initial values for the distances from source node( in our case B) to every other node in the graph.

2) At each step, the shortest distance from node s to another node is determined.

In our case, B is source and D is sink.

Step 1:

Assign the zero distance value to node s, and label it as Permanent.

The state of node B is (0, p).

Assign to every node a distance value of 1 and label them asTemporary. The state of every other node is (1, t).

Designate the node B as the current node

The set of nodes with temporary labels that can be reached from the current node are C, P, and H. Update the distance values of these nodes.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.