CS theory Problem 6: CS Data and Algorithm Analysis question In a directed graph
ID: 3830349 • Letter: C
Question
CS theory Problem 6: CS Data and Algorithm Analysis question
In a directed graph, let P be the second shortest path between two nodes s and t in the graph. To be precise, the length of P is larger than the shortest path length from s to t but less than or equal to the length of all other s-t paths. Let v be a node on this path. We will use the notation P(s, v) to denote the sub-path of P from s to v and P(v, t) to denote the sub-path of P from v to t. (a) Prove that at least one of the following statements is true: (a) P(s, v) is the shortest path from s to v or (b) P(v, t) is the shortest path from v to t. (b) Suppose that v is a node such that P(v, t) is the shortest path from v to t. What can you say about P(s, v)? I just want a single sentence answer.Explanation / Answer
a)
P (s-t) indicate SECOND shortest path.
Let v be the any node beween this path s-t.
(case a)
Let us assume that P(s,v) is the shortest path ……..
P(s-t)= P(s,v) + P(v,t) -----------------(1)
As P(s,v) is shortest P(v,t) has to be SECOND shortest distance to make P(s,t) as Second shortest distance.
(case b)
Let us assume that P(v,t) is the shortest path ……..
P(s-t)= P(s,v) + P(v,t) -----------------(1)
As P(v,t) is shortest P(s,v) has to be SECOND shortest distance to make P(s,t) as Second shortest distance.
So atleast case a or case b has to be true if both are true then P(s-t) will be shortest distance.
b)
As explained above case b if P(v,t) is shortest path p(s,v) will be second shortest distance.