Corresponding author: Deepak Tatyaji Ahire (
Academic editor:
This article puts forth all the existing methods proposed by the various authors of the Stack Exchange community to find all the edges on any shortest path between two given nodes of a directed acyclic graph. For a directed acyclic graph with
The authors declare no conflict of interest.
In this article, we have discussed all the existing methods proposed by the various authors of the Stack Exchange community to find all the edges on any of the shortest paths between two given nodes of a directed acyclic graph. For a directed acyclic graph with
The ranking of any page on the search engine depends on several factors and it is not significantly affected by the number of upvotes or downvotes received for a particular answer (
Currently, there is no reliable mechanism to link any answer posted on the Stack Exchange page to different use cases other than the question on that page which, in turn, reduces the chances of these answers being referenced on various other pages with relevant content and hence resulting in a lower page rank. As content is also one of the critical aspects of search engine optimisation (
Finally, it acknowledges the time and the efforts of the moderators and other contributors to write precise answers and share their advice and opinions. Several new users who do not have accounts on the Stack Exchange community access these helpful posts, but leave without expressing their feedback and votes (
Table
The following are the existing approaches:
Computing all possible paths and sorting them to find all the shortest paths is a brute force approach and is not the feasible solution to execute the program in polynomial time, as the maximum number of paths in a directed acyclic graph can be exponential and the runtime will be of the order of Ω(
Rather than computing all the paths, one might be tempted to only focus on the shortest paths. However, in the worst case, the number of shortest paths also can be exponential. Stack Exchange users
Computing the total number of paths between two given nodes in linear time of O(
Railway station routing algorithm using the backtracking method (
Computer Science Stack Exchange user
For equation 1, 
If the edge
This approach has a runtime of the order of O(
Math Overflow user
To find all the edges that are not part of any shortest path (
To check if a vertex is along some possible shortest path from
Computer Science Stack Exchange moderator
Suppose the single source shortest path distances from
and
For equation 2 and equation 3, 
If the edge
This approach has the runtime of the order O (2*
Bidirectional Dijkstra (
Maintaining a set of all the parent nodes (the node from which the arrow is directed is a parent node) for each node, if it is reachable with the minimum possible distance from source
While applying the relaxation process for each edge, if the path's cost to reach a particular node from source
Now, a new graph is constructed using each nodes' beneficial parents set. Unweighted edges from all the nodes, directed towards all of their respective beneficial parent nodes, are added.
Fetch all the edges encountered during the reverse BFS (starting from
Stack Overflow user
This approach has the runtime of the order O((
Printing paths in Dijkstra's shortest path algorithm (
From most of the references mentioned, it is evident that there is a considerable gap between the number of views and the number of upvotes. Less than 10% of the viewers have voted for the answers. Most of the hits on the community pages are because of search engine recommendations dependent on many factors. Several new beneficiaries without an account on the community portal access these helpful posts and leave without expressing their feedback and votes (
Therefore, this article also appeals to all the beneficiaries to use their privileges responsibly and the experienced users to encourage others to write and improve answers instead of a downvote. Recently, the Stack community also started encouraging the users to vote for the helpful posts and experimented with the features like reaction buttons as a way for users to thank the authors (
The authors declare no conflict of interest.
Abbreviations used in the article



The given directed acyclic graph. 

The number of nodes. 

The given source node. 

The given destination node. 

The total number of paths between 

The edges in the graph 

The number of edges in the graph 

A twodimensional array used to store all pair shortest paths computed using dynamic programming. 
A onedimensional array used to store the single source shortest path distance. The value at the index represented by the 