How to find all the shortest paths between u and v in an undirected graph in O(|V|)?

Question

The graph G is an undirected graph, and all its edges' weight are same. u,v are 2 given vertices, how to find the number of the shortest paths between u and v in graph G in O(|V|)?

|V| stands for the number of vertices in G.

Answer 1

Because Dijkstra is greedy and keeps consuming paths in increasing order. When a negative weight would be discovered later on, this could mean an earlier found path is no longer the shortest path, and therefore Dijkstra fails.

Example:

A -> B (5)
A -> C (5)
C -> B (-10)

Dijkstra will find A->B (5) being the shortest path from A to B, but in reality, the shortest path will be A-> C -> B (-5)