0
$\begingroup$

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after execution of Floyd Warshall. We were asked to think about why this is not $O(n(n+m))$ and for which graphs we really would have to do $O(n^2)$ work and if it really is $O(n^2)$ for these graphs.

The Output should be all shortest paths trees $T_v$ for any $v \in V$

I can clearly see running DFS on every node as start node and checking if an edge is part of the shortest path or not results in O(n(n+m)) which doesnt give the desired result.

I came up with the following ideas:

  • I thought about if I can state that n >= m/2 if we exclude all isolated nodes in $O(n)$ first, so $O(n^2) = O(nm)$ what would result in $O(nm)$ over all.
  • Another possibility regarding DFS would be adding edges for other trees which hold the same edge. I came up to use a $nxm$ Matrix wheter a node was added or not and keep track of visited nodes to add edges for every node. But since I have to go through all nodes every time and check for matrix entry, which does not improve that much over all.
  • I also thought about path construction using a next matrix, which can be created during floyd warshall though I have to do it for every combination of two nodes in two for loops and every one recursive call is worst case $O(n)$ which results in $O(n^3)$. It would get better only if a can skip loops and edges though I can´t see an efficient way to achieve this.

Do you see any flaws within in my statements above and might any of these possibilites leed to the disired outcome? How can it be solved?

$\endgroup$
2
  • $\begingroup$ Can you clarify what the output should be? A graph $H$ such that $e$ is in $H$ if and only if $e$ is in at least one SPT? Any shortest-path tree $T_v$ for each $v \in V$? A graph $H_v$ for each $v \in V$ such that $e$ is in $H$ if and only if $e$ is in at least one shortest path tree from $v$? Are edge weights non-negative? $\endgroup$ – Steven Feb 11 at 19:58
  • $\begingroup$ Output would be all $T_v$ and we can have negative edges. I clarified above, thx! Though no negative cycles. $\endgroup$ – FelixOuttaSpace Feb 11 at 20:15
1
$\begingroup$

Compute all pair to pair distances $D[u,v]$ for $u,v \in V$ using Floyd-Warshall.

For each vertex $s \in V$ construct a graph $H_s$ as follows:

  • For each edge $e = (u,v)$ check whether $D[s,u] + D[u,v] = D[s,v]$. If the answer is yes the (directed) edge $(u,v)$ belongs to at least one SPT from $s$, and you add $e$ to $H_s$.

This requires time $O(n \cdot m)$ and each graph $H_s$ is encoding all SPTs from $s$. To get a single SPT from $T_s$ each $s$ compute any spanning arborescence of $H_s$ rooted in $s$. This can be done, e.g., via a BFS.

$\endgroup$
4
  • $\begingroup$ so running n times BFS would still be $O(n(n+m))$? $\endgroup$ – FelixOuttaSpace Feb 11 at 20:28
  • $\begingroup$ Yes, a BFS takes time $O(n+m)$, where $n$ and $m$ are the number of vertices and edges of the graph. Each graph $H_s$ has $n$ vertices and at most $m$ edges. $\endgroup$ – Steven Feb 11 at 20:34
  • $\begingroup$ ok would stating $m \geq n/2$ make $𝑂(𝑛(𝑛+𝑚)) = O(mn)$ since $n^2 \leq 2mn$ because $H_s$ won´t hold unconnected components. $\endgroup$ – FelixOuttaSpace Feb 11 at 20:38
  • 1
    $\begingroup$ If $m = \Omega(n)$ then $O(n(n+m)) = O(nm)$. You can safely assume that $m = \Omega(n)$ since otherwise you can restrict yourself to the graph induced by the vertices of degree $\ge 1$ in time $\tilde{O}(m)$. $\endgroup$ – Steven Feb 11 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.