Number of shortest paths in weighted graph

Question

This is the question: Given a directed graph G=(V,E), a source vertex s $epsilon V, we know that all cycles in G are of positive weight ( > 0). Also we are given the graph after Bellman-Ford was run on it, meaning that for each v in V we know both d[v] (shortest path from s to v) and pi[v] (v's predecessor)

Describe an algorithm to find the number of shortest path from s to v for all v in V. The algorithm must run in O(V+E)

*We cannot edit the Bellman-Ford run on the algorithm

This is what i thought of: We run a modified DFS,

Algorithm(G,s):

1.DFS-Visit(G,s)
2. return count[v] foreach v in V

DFS-Visit(G,u):

1.foreach v in Adj[u]
   2.if d[v] == d[u] + w(u,v) && (u,v) is not a backedge
      3.count[v] = count[v] + 1
      4.DFS-visit(G,v)

*It seems like the algorithm can get stuck in an infinite loop, maybe i can ignore back-edges? (since a shortest path will always be simple)

*This is not a duplicate of How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

in that question the graph is unweighted here it is weighted ( edges) Do you think this is correct? Thanks

Answer 1

if d[v] == d[u] + w(u,v) && (u,v) is not a backedge

The condition d[v]==d[u]+w(u,v) is the most important here. If guarantees that this is never a backedge and, moreover, it guarantees that you will never return to the vertex where you have been.

Indeed, assume you returned to a vertex where you have been. Then you have

d[v1]==d[v0]+w(v0,v1)
d[v2]==d[v1]+w(v1,v2)
...
d[v0]==d[vn]+w(vn,v0)

summing it all, we find that

w(v0,v1)+w(v1,v2)+...+w(vn,v0)==0

that is a zero-weight loop, but we are told there is no such loops.

So this algorithm will never stuck into a infinite loop; moreover, if you leave only the edges satisfying d[v]==d[u]+w(u,v) (making graph directed even if it has not been), the resulting graph will be acyclic.

Therefore you can run the standard algorithm of finding a number of ways in an acyclic graph. In fact this is what you have already written (your DFS), just note that

count[v] = count[v] + 1

should be

count[v] = count[v] + count[u]