New answers tagged weighted-graphs
2
You can solve this in $O(|V| \cdot |E|)$ time.
Construct a digraph with vertices of the form $\langle v,b\rangle$ where $v \in V$, $b \in \{0,1\}$, as follows: for each edge $v \stackrel{t}{\to} w$ in your graph, add the edges $\langle v,b \rangle \to \langle w,b + t \bmod 2 \rangle$ for each $b \in \{0,1\}$ to the new graph.
Then, for each $v \in V$, ...
2
Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.
What ...
0
Let us say that an edge $e$ in $G$ is BAD if there exists a cycle in $G$ in which $e$ has maximum weight.
Define ${\cal B}=\{e~|~e$ is BAD in $G\}$ to be the collection of all bad edges.
Your question is whether the graph $(G - {\cal B})$ the MST of $G$ (assuming all edge-weights are distinct). The answer is YES!
In order to prove this it suffices to ...
0
Sorry if I didn't understand your question, but what I think you meant to ask is, whether it is possible for an edge to not be in a MST if this edge is not in a cycle.
Here's my answer.
Let us assume that we have an edge (u,v) in a graph G, that isn't part of a cycle. This would mean that there is no path from u to v that isn't the edge (u,v).
If the edge (...
1
On the question from title
For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order:
$$
d(v)=
\begin{cases}
0\text{ if } v = s\\
-\infty \text{ if } v \not= s \land v \in S\\
1 + max_{(v, u) \in E} d(u)
\end{cases}
$$
You can run this algorithm for every $s \in S$ to get the ...
0
It's possible to use BK-Trees to speed this up. Inserting $n$ elements into the tree takes $O(n \log n)$ time. After this you can query the tree for all strings whose edit distance is exactly one away from your input. Doing this for all strings again takes $O(n^2)$ complexity, however with a very small constant factor (this page mentions only 5-8% of the ...
0
Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$.
Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given ...
1
What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph?
for i in V:
weight(i) = 0
for e=(i,j) in E:
weight(i) = weight(i) + weight(e)
weight(j) = weight(j) + weight(e)
0
I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's.
First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column i and j corresponds to the shortest distance from vertex i to vertex j.
Second, to mark the all-path shortest paths' path, you simply ...
Top 50 recent answers are included
