Given a directed weighted graph with n vertex and m arc (n < 1500, m < 5000) and one arc (u, v). And answer the question is how many shortest paths (can begin at any position a and end in b such that a! = b) passes through a given arc.
Example:
n = 4, m = 4
arc (1, 2) with weight is 5
arc (2, 3) with weight is 5
arc (3, 4) with weight is 5
arc (1, 4) with weight is 8
and arc (1, 2).
The answer is 2 because arc (1, 2) in shortest path 1->3 and 1->2.
Dijkstra can solve this problem?
One quick thought is, since it's all about path reconstruction, you may use Floyd-Warshall's algorithm for finding shortest path between every pair of nodes in much cheaper way compared to running Dijkstra's algorithm for every node. After that, by doing path reconstruction for every node, you simply check if the provided arc exists on the path found.
(Note however that Floyd-Warshall's algorithm does not support graphs with negative cycles)
First, find out the shortest path between u and v using Dijkstra's algorithm. Interestingly, if the shortest path between u and v is not the edge uv, then no shortest path between any 2 points will ever contain the edge uv. In such a case, you can submit your answer as 0.
Now we may proceed to apply Floyd Warshall's algorithm O(n^3) once or Dijkstra's algorithm using a Fibonacci heap O(m+n*logn) on every node which totals to be O(n*m + (n^2)*logn). I would normally recommend Floyd Warshall, but since max value of m does not seem to be the order of n^2 for the maximum value of n, Dijkstra's algorithm on multiple nodes might become viable if you use a Fibonacci heap. (m and n may just be large enough to compensate for the huge constants while using the latter.)
Next,
From every point "a" see if shortest path length to "u" + len(u->v) + shortest path length from "v" to "b" is = shortest path length from "a" to "b". This should take constant time for every check since we already have a table of the shortest paths. That'll come out to be the order of
n choose 2that isO(n^2)
For all a and b, where it is true, you'll have to find out if there are multiple shortest paths that exist. This one is going to be a pain. Neither Dijkstra's Algorithm nor Floyd Warshall's algorithm, gives you a way to find all shortest paths between any 2 points. They only guarantee a shortest path. One way to brute force it could be to identify one shortest path and change one edge at a time to see if a new shortest path emerges!
This whole process should still be faster than constructing all possible paths, checking if it is the shortest and finally checking if it passes through the required edge. However, I am keen to find out if the latter part of my prescribed algorithm may be optimized or altered.
Edit: Since the Graph is known to be a Directed Acyclic Graph, there is no need to apply Bellman ford in the start. If you want to know how negative edge-weight cycles are identified in directed graphs, please read about Johnson's Algorithm.
