How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

by

Here are some ideas on this.

  • There can only be multiple shortest paths from v->w through node x, either if there are multiple paths into x through the same vertice or if x is encountered multiple time at the same DFS level.

Proof: If there are multiple paths entering x through the same vertex there are obviously multiple ways through x. This is simple. Now let us assume there is only one way into x through each vertex going into x (at maximum).

If x has been encountered before, none of the current paths can contribute to another shortest path. Since x has been encountered before, all paths that can follow will be at least one longer than the previous shortest path. Hence none of these paths can contribute to the sum.

This means however we encounter each node at most once and are done. So a normal BFS is just fine.

  • We do not even need to know the level, instead we can get the final number once we encounter the final node.

This can be compiled into a very simple algorithm, which is mainly just BFS.

 - Mark nodes as visited as usual with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
 - If a node that has been visited should be added ignore it.
 - If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
 - Propagate the counts on the queue when adding new nodes.
 - when you encounter the final, the number that is stored with it, is the number of possible paths.

More Related Contents:

  1. Finding all the shortest paths between two nodes in unweighted undirected graph
  2. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  3. graph – Dijkstra for The Single-Source Longest Path
  4. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  5. Data structures for loaded dice?
  6. Cycles in an Undirected Graph
  7. Breadth First Vs Depth First
  8. How to implement a queue using two stacks?
  9. Computing set intersection in linear time?
  10. Graph auto-layout algorithm
  11. How to delete in a heap data structure?
  12. What is the difference between tree depth and height?
  13. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  14. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  15. How to implement depth first search for graph with a non-recursive approach
  16. Why is the time complexity of both DFS and BFS O( V + E )
  17. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  18. O(klogk) time algorithm to find kth smallest element from a binary heap
  19. Enumerating all paths in a directed acyclic graph
  20. Skip List vs. Binary Search Tree
  21. Hashing a Tree Structure
  22. Why DFS and not BFS for finding cycle in graphs
  23. How can I return an array of struct in solidity?
  24. Planar Graph Layouts
  25. The intersection of all combinations of n sets
  26. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  27. Why use binary search if there’s ternary search?
  28. Bridges in a connected graph
  29. What are probabilistic data structures?
  30. Given a set of intervals, find the interval which has the maximum number of intersections

Leave a Comment