Longest path from subset of nodes to all nodes with 0/1 lengths
Diego Olivier Fernandez Pons
nodes of interest in the graph.
I need the longest path from all the nodes in S to all the nodes in
the graph.
Does anyone has a better suggestion than running |S| times a
Dijsktra ?
Example
1 -> 2 length 1
2 -> 3 length 0
3 -> 4 length 1
1 -> 4 length 1
S = {4}
The application is the following : I have a precedence graph on nodes
that have a property that we will name here "color". There are nodes
that are "transparent". I am looking for the colors of the direct
predecessors knowing that the transparent nodes just inherit the
colors of their own direct predecessors.
In the example
1 is blue
2 is red
3 is transparent
We want to know the color of the direct predecessors of 4 (that is
{2})
In this case 1 is not a "direct" predecessor even if there is a link
between 1 and 4 because there is also a chain 1 -> 2 -> 3 -> 4.
To get to a shortest path problem, reverse all the links, give a 1
distance to all the arcs that arrive to a non-transparent node, 0
otherwise, compute the longest paths and take all the nodes which are
at a distance of 1 from the original node.
Diego Olivier
Paul
On Oct 18, 6:54 pm, Diego Olivier Fernandez Pons
On a graph with n vertices, Floyd-Warshall is O(n^3) to get the
shortest paths between every pair of nodes, which is more than you
need. Hard to say whether it works out to be any faster than running
Dijkstra from every node in S to every node outside S.
But you can reduce the number of target nodes, can't you? Do the
reversal described in your last paragraph and, for each node s in S,
find all non-transparent nodes x such that either (s, x) is an arc or
there is a path s -> x with all intervening nodes transparent. Then
compute the longest distances just for those pairs of nodes (using
Dijkstra).
I'm not sure (graph algorithms are not my specialty), but I think it
still might be possible that Floyd-Warshall would be faster.
Cheers,
Paul
Diego Olivier Fernandez Pons
> On a graph with n vertices, Floyd-Warshall is O(n^3) to get the
> shortest paths between every pair of nodes, which is more than you
> need. Hard to say whether it works out to be any faster than running
> Dijkstra from every node in S to every node outside S.
There are a couple of reasons to believe the problem should simplify
considerably with 0/1 valued arcs.
Assume all the arcs are of length 1. Then Bellman-Ford reduces to BFS
which complexity is O(m), thus you can do it | S | * m
Actually, there is a complete solution linear in the number of arcs
1. The topological sort of the nodes of a graph is linear in the
number of arcs : O(m)
- compute the entering degree of each node -- O(m)
- for all nodes without entering arcs, decrease the entering degree of
all successors -- O(n) + bookkeeping
2. You only need to perform the second step once for each node in S
(because you only need the nodes of rank 1)
In other words, you can factor the first step and you end with an
algorithm in m + |S| * n
That is what makes me believe the result can be achieved in better
theoretical and practical complexity than |S| n^2 or n^3.
Diego Olivier