An instance of PATH is given by  where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t.DISTANCE-PATH is similar, but with an extra requirement d and on an undirected graph. A true instance of this would be  where G is an undirected graph and there exists a path of length d from s to t, and there isn't a shorter path.Given directed , construct an undirected G' such that G' has a path from s to t of shortest length d iff G has a path from s to t.The idea is to construct G' by making n copies of G, and each edge in G' connects one copy to the next.I don't understand how d comes into play and how to ensure there are no shorter paths, should d be the number of copies of G made? Should G' connect the copies of G by connecting one t node to the next s node? I'm not sure how to approach this problem
Log reduce PATH to DISTANCE-PATH
complexity theory;graphs;reductions