Modify Dijkstras algorithm to count the number of shortest p

Modify Dijkstra’s algorithm to count the number of shortest paths from the start node to each other node. It will still need to determine the length of the shortest path from the start node to each other node as well.

Solution

let me summarise as follows:

1) It is a directed graph
2) It asks for the number of different shortest paths. First the paths should be shortest, then there might be more than one such shortest paths whose length are the same between v and w, so both from v to w and from w to v should be counted.
linear-time.
3) The graph is not weighted.
From the above points have following thoughts:

1) I don\'t need to use Dijkstra’s Algorithm because the graph is not weighted and we are try to find all shortest paths, not just single one.
2) I maintain a count for the number of shortest paths
3) I would like to use BFS from v first and also maintain a global level information
4) I increase the global level by one each time then BFS reaches a new level
5) I also maintain the shortest level info for shortest path to w
6) The first time I meet w while traveling, I assign the global level to the shortest leveland count++;
7) as long as the global level equals to the shortest level, I increase count each time I met w again.
8) if the global level becomes bigger than the shortest level, I terminate the travelling, because I am looking for shortest path not path.
9) Then I do 2 - 8 again for w to v