Design an efficient algorithm for shortest path and.. Design and analyze an effi

Question

Design an efficient algorithm for shortest path and..

Design and analyze an efficient algorithm for the following problem: given is an adjacency list for a digraph G = (V, E} and three distinguished vertices a, b, and c epsilon V . The output is a shortest path from a to c that passes through b. Describe the idea of the algorithm, provide pseudo - code, and give the runtime in terms of the size of the graph. In a group of five people, for any three of them, there are always two who know each other, and there are two who not know each other. Prove that these five people can sit at a round table in such a way that every person will have people he/she knows on both sides.

Explanation / Answer

5. You can run dijikstra's twice.
once run it from point a. It will give you shortest path to c.
Then run it from point c. It will give you shortest path to b.
hence shortest path from a to b passing through c is a->c + c->b
time complexity of dijikstra is O(n*n). Hence in the above problem, total time complexity is. 2*O(n*n), which can be written as O(n*n).

6. this is a simple graph question.. suppose you draw a pentagon, where each adjacent nodes are known people and non adjacent nodes are not known people... whenever you pick any 3 nodes of the pentagon, it becomes necessary to choose 2 adjacent nodes among them. hence two will always be knowing each other and one will not.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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