Seven families live in the little village Zen. They live in seven separate h Eac

Question

Seven families live in the little village Zen. They live in seven separate h Each house is connected to the other six via six different roads. The length of each road is also given. (In other words, if you represent a house as a node, and a road as an edge between two nodes, you will obtain a complete graph. The weight of each edge is the length of the corresponding road.) Given a pair of houses in Zen, h_s and h_e, design to find the shortest path from h_s to h_e that passes at most two different roads. Describe your algorithm in pseudo code with concise comments.

Explanation / Answer

v= number of families in the village which is 7 as per Q

Void Shortest_Path(int Graph[][v])

{

int dist[v][v] j,k,i;

for(i=0;i<v;i++)

{

for(j=0;j<v;j++)

{

dist[i][j]=Graph[i][j];

}

}

for(k=0;k<v;k++)

{

for(i=0;i<v;i++)

{

for(j=0;j<v;j++)

{

if(dist[i][j]>dist[i][k]+dist[k][j])

dist[i][j]>dist[i][k]+dist[k][j];

}

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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