jankit366's blog

Least number of Unique Edges from A and B to D
By jankit366, history, 2 months ago, In English

A and B wants to reach some destination in an undirected graph using the least number of unique edges. Find the count of unique edges.

Let's say the two paths come out to be this.. A-x-y-D B-y-D

Output : 4

Explanation : A-x, x-y, y-D and B-y

Follow up: What if there are multiple sources?

Can someone help me to solve this optimally?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jankit366 (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Do a BFS from nodes A, B and D, now you know the distance from A, B and D to every node. There are two cases:
1) the paths A — D and B — D don't intersect
2) the paths meet at some node X(A — X — D and B — X — D)

the first case is just $$$d_{DA} + d_{DB}$$$
in the second case to find the node X we can just try for every node $$$d_{AX} + d_{BX} + d_{DX}$$$

→ Reply