New answers tagged graph-traversal
1
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)$ ...
1
You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.
Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it contains a simple path of length $n-1$. This is a well-known $\mathsf{NP}$-hard problem.
Construct $G$ from $H$ by adding two vertices $x$ and $y$, the edges $(...
3
Following is a simple counterexample: Take a complete graph on four vertices: ${u_{1},u_{2},u_{3},u_{4}}$, with edge weights $w(u_{1},u_{2}) = 1$, $w(u_{2},u_{3}) = 2$, $w(u_{1},u_{3}) = 4$, $w(u_{1},u_{4}) = 5$, $w(u_{2},u_{4}) = 3$, and $w(u_{3},u_{4}) = 6$. Here MST is composed of edges: $(u_{1},u_{2})$, $(u_{2},u_{3})$, and $(u_{2},u_{4})$ with total ...
0
It seems to me that you are confusing the graph itself with the search tree produced by some search procedure.
As you state, you can't go from one node to the next unless that node knows its neighbors (and not only its own parent). But the search tree is (perhaps implicitly) generated from a search procedure you perform on the actual graph. Perhaps this is ...
Top 50 recent answers are included
