Give an algorithm to compute all Z-path reachable node pairs in the digraph G.

Let G = (V, E) be a weighted, directed graph with weight function w: E rightarrow {-1, +1}. The weight w(p) of a path p is the sum of all edge weights in thepath. We say a path p is a Z-path iff its path weight w(p) is 0, and any positive edge (i.e., the edge with +1 weight) appears after all negativeedges (i.e., the edges with -1 weights) in path p. For example, the path " -1, -1, +1, +1" is a Z-path but "-1, +1, -1, +1" is not. A node upsilon in V is Z-path-reachable from node u iff there is a Z-path p from u to upsilon inG. Give an O(EV)-time algorithm compute the all Z-path-reachable node pairs inthe digraph G. Note that the graph can contain negative cycles