O(E+V) algorithm to compute number of shortest paths between 2 nodes on given graph

0
votes

When Given a graph G with vertices and edges |V| and |E| respectively and vertices u and t, write a O(|E|+|V|) algorithm to compute the number of shortest paths from u to t, i.e. if there are 5 paths of length 4 with length 4 being the shortest path from u to t then the algorithm will output 5.

I know that the algorithm must somehow incorporate either a DFS or a BFS due to its run-time as each have a O(|E|+|V|) run-time, but I am a bit stuck. I tried implementing something where it would do a DFS repeatedly with the algorithm terminating at t but it this became problematic for deciding which nodes to set as visited and which to reset after each iteraition.

Thanks in advance!

1
algorithmgraph-theorydepth-first-searchbreadth-first-search
This is basically a variant of Dijkstra's algorithm. – Willem Van Onsem
@WillemVanOnsem yeah I was considering an implementation of Dijskta's with a couple changes but doesn't it have a o(|V|+|E|logE) due to having to create a priority queue and update it each time – Joe Butler
With the naïve priority queue implementation (ie start with all vertices in the PQ), it'd be O(V log(V) + E). But you don't have to start with all the vertices in the PQ. – bjb568
@bjb568 yeah but how would you know which vertices to include, and wouldn't that runtime still be greater than O(E+V)? – Joe Butler
The reason Dijkstra's algorithm uses a priority queue is that some edges are more expensive than others. That's not the case for you, so you don't really need the priority queue -- you can just use a normal FIFO queue -- and Dijkstra's algorithm reduces to just breadth-first search. – ruakh

1 Answers

1
votes

You can use breadth-first search. For each vertex, keep track of:

  • the shortest path length from u to that vertex
    • Whenever you process a given vertex, you set this property for all of its neighbors that don't already have this property set.
    • This doubles as a "has already been enqueued" flag: you initially set to a sentinel value such as ɴɪʟ or ∞, and only update it once for any given vertex. So you don't need a separate flag to track visited vertices.
  • the number of shortest paths from u to that vertex
    • Whenever you process a given vertex, you increase this property appropriately for all of its neighbors whose shortest path length from u is greater than that of the vertex you're processing.
    • Note that you'll update this property many times for some vertices, but that's OK, because you only update it once per edge.