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?