Algorithm to find the number of shortest paths
Given an undirected（no lengths） graph G=(V,E) with |V|=n and |E|= m, and two vertices v,w, find the algorithm that outputs the number of shortest v-w-paths in G. The running time should be O(m+n)
I have been working with this problem but have difficulties to let the running time be O(m+n)
Since this graph is both undirected and unweighted, I have tried this way. Use BFS to determine the length of the shortest v-w-path. Then use DFS to find the number of the v-w-shortest paths such that two nodes are connected and the length of path equals to the output of BFS. But the running time of this plan is O(m+n)+O(m+n).
Also I've tried to modify the Dijkstra algorithm. Store the length of the shortest path and the number of the shortest path when there is a node adding to the set of visited nodes. And I 'm stuck with the computation of running time.
Answer
This question may be looking for a modification of Dijsktra's algorithm. With Dijkstra's algorithm you maintain, for each node, the length of the shortest path to that node, and you update this at a node based on the shortest path to a neighbouring node and the length of the simple link from that neighbouring node to the node in question.
At each node you could keep, as well as the length of a shortest path to it, a table of the nodes that can precede it on a shortest path to it, and the number of shortest paths to that node, which should be the sum of the number of shortest paths to these neighbours. When you find a new shortest path to a node you either delete all of this information (if the new shortest path is shorter than before) or update the entry in that table for the second last node in the path, if the new path is the same length as the previous shortest path to that node.