Research Ideas and Outcomes :
Commentary

Corresponding author: Deepak Tatyaji Ahire (ahiredeepak20@gmail.com)
Received: 12 May 2021  Published: 25 May 2021
© 2021 Deepak Ahire, Omkar Jadhav
This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Citation:
Ahire DT, Jadhav OS (2021) Commentary  Methods to find all the edges on any of the shortest paths between two given nodes of a directed acyclic graph. Research Ideas and Outcomes 7: e68600. https://doi.org/10.3897/rio.7.e68600

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 N number of nodes, an exponential number of paths are possible between any two given nodes and, thus, it is not feasible to compute every path and find the shortest ones in polynomial time to generate a set of all edges that contribute or make any of the shortest paths. The methods discussed in this article are not limited only to this specific use case, but have a much broader scope in graph theory, dynamic programming and counting problems. Generally, various other questions and answers, raised on the community portal having similar scope to those that the users specifically seek, do not receive sufficient hits and, hence, enough attention and votes for various reasons worth contemplating. Therefore, this article also aims to highlight the various scopes of the methods discussed in this article and acknowledge the efforts of the authors, moderators and contributors of the Stack Exchange community for their expertise and time to write precise answers and share their opinions and advice. Finally, it also appeals to all the other beneficiaries in the community to use their privileges responsibly and upvote the posted answers, if they helped solve their queries, as one upvote is free of cost.
Shortestpath, Dijkstra, Singlesourceshortestpath, Alledgesonanyshortestpath, Directedacyclicgraph, StackExchangecommunity, Allpossibleshortestpaths, StackExchangeprivileges, Upvote
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 N number of nodes, an exponential number of paths are possible between any two given nodes and, thus, it is not feasible to compute every path and find the shortest ones in polynomial time to generate a set of all edges that contribute or make any of the shortest paths. The methods discussed in this article are not limited only to this specific use case, but have a much broader scope in graph theory, dynamic programming and counting problems.
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
Abbreviation  Definition 
G  The given directed acyclic graph. 
N  The number of nodes. 
S  The given source node. 
D  The given destination node. 
P  The total number of paths between S and D 
E  The edges in the graph 
M  The number of edges in the graph 
Dist  A twodimensional array used to store all pair shortest paths computed using dynamic programming. Dist[U][V] holds the value of the shortest possible distance between the nodes U and V, where U, V ∈ G. 
Dist{U}  A onedimensional array used to store the single source shortest path distance. The value at the index represented by the i^{th} node, i.e. Dist{U}[i], holds the shortest distance from the source U to node i. 
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 Ω(N + (P * log(P))) (
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 Raphael and unkulunkulu proposed an example in which all the possible paths between S and D are the shortest and their number is exponential. In both the examples, the number of paths is of the order O(2^N) and, therefore, it was clear that P will dominate this approach (
Raphael also provided another example of a graph with an exponential number of shortest paths (
Computer Science Stack Exchange user Draconis proposed an approach using the Floyd Warshal algorithm. The first step is to compute all pair shortest paths. Then, for every edge e(U, V), where e ∈ E and U, V ∈ G, check if it satisfies the following equation:
Dist[S][U] + e(U, V) + Dist[V][D] = Dist[S][D] eq(1)
For equation 1, e(U, V) represents the edge weight of the directed edge e(U, V).
If the edge e ∈ E satisfies equation 1, then edge e belongs to the shortest path.
This approach has a runtime of the order of O(N^3 + M) (
Computer Science Stack Exchange moderator D.W. proposed an approach which uses a singlesource shortest paths algorithm (e.g. Dijkstra's algorithm) twice, ones from S to all the nodes and then from D (treating it as the source) to all other nodes after reversing the edges of the graph (
Suppose the single source shortest path distances from S to all other nodes are stored in Dist{S} and the singlesource shortest path distances from D to all other nodes are stored in Dist{D}, then, for every edge e(U, V), where e ∈ E and U, V ∈ G, check if it satisfies any one of the following two equations:
Dist{S}[U] + e(U, V) + Dist{D}[V] = Dist{S}[D] eq(2)
and
Dist{S}[U] + e(U, V) + Dist{D}[V] = Dist{D}[S] eq(3)
For equation 2 and equation 3, e(U, V) represents the edge weight of the directed edge e(U, V).
If the edge e ∈ E satisfies equation 2 or equation 3, then edge e belongs to the shortest path.
This approach has the runtime of the order O (2*M + N * log(N)) + M) ~ O(M + N * log(N))) when the Fibonacci Heap is used to implement the Dijkstra's algorithm (
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 S via those particular parent nodes is the most important technique used in this approach. This technique helps reducing one extra call to Dijkstra's algorithm in the reverse direction from D (acting as source), as discussed in the previous approach.
While applying the relaxation process for each edge, if the path's cost to reach a particular node from source S via any of its parent nodes improves, then that parent node becomes part of the node's new beneficial parents set and the previous set, if any, is discarded. If the path's cost to reach a particular node from source S via any of its parent nodes remains the same as the previously computed minimum cost, then that parent node is just added to the node's previous beneficial parents set.
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 D as the source towards S as the destination) on the new graph. The reverse of these edges represents all the edges on any shortest paths in the original graph.
Stack Overflow user Ziyao Wei proposed this approach (
This approach has the runtime of the order O((M + N * log(N)) + (M + N)) ~ O(M + N * log(N)).
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.