Intereting Posts

How can I quickly know the rank of this / any other matrix?
equilibrium distribution, steady-state distribution, stationary distribution and limiting distribution
If $a,b$ are integers such that $a \mid x$ and $b \mid x$ , must $\mathrm{lcm}(a,b)\mid x$?
Is there an example of a sigma algebra that is not a topology?
Probability of iid random variables to be equal?
Economic price optimisation problem
$\arcsin$ written as $\sin^{-1}(x)$
Question for understanding definition of point process
An exercise in Kunen
How do we describe standard matrix multiplication using tensor products?
Intersection of two arcs on sphere
Measure of countable union
Difference between $\sum$ and $\int$
Proof that $\int x^x dx$ can't be done in terms of elementary functions?
Sum of the reciprocal of sine squared

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there’s an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it finds the shortest path (by weights) which contains an even number of edges. (I can assume it doesn’t have a negative cycles).

Obviously I need to use Bellman-Ford with complexity of $O(|V||E|)$, but how do I manipulate it in such way that the paths will contain an even number of edges?

Thanks!

- Least Impossible Subset Sum
- How does Mathematica solve $f(x)\equiv 0\pmod p$?
- Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$
- Twenty questions against a liar
- Non-revealing maximum
- Extended Euclidean algorithm with negative numbers

- How can I solve $8n^2 = 64n\,\log_2(n)$
- Polynomial Question
- Finding location of a point on 2D plane, given the distances to three other know points
- Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?
- Quickest way to determine a polynomial with positive integer coefficients
- Simplifying polynomials
- What math should a computer scientist take in college?
- Honest and Deceitful Professors Problem
- Computational complexity of least square regression operation
- easy to implement method to fit a power function (regression)

Create a new graph with the vertices being $V\cup V’$ where $V’$ is a replicate of the vertices of $G$ (meaning $\mid V’\mid=\mid V\mid$ and the sets are disjoint).

The edges are: $$e’=(i,j’)\in E’ \iff e=(i,j)\in E$$

$$e’=(i’,j)\in E’ \iff e=(i,j)\in E $$

(there are no edges of the form $(i,j),(i’,j’)$.

The weights are $w'((i,j’))=w'((i’,j))=w((i,j))$.

Now, any path from $i$ to $j$ must be of even length (paths of odd length end up in $V’$ and not in $V$).

Now you can use Bellman-Ford.

You can do something similar as in this answer: Maintain two separate distances from the source to each vertex, one for paths with an odd number of edges, one for paths with an even number of edges. In each update, use the odd ones to update the even ones and vice versa.

- Parallel surface
- An example of a sequence of Riemann integrable functions $(f_n)$ that converges pointwise to a function $f$ that is not Riemann integrable.
- Strategies and Tips: What to do when stuck on math?
- Help with $\int \frac 1{\sqrt{a^2 – x^2}} \mathrm dx$
- An abelian group of order 100
- Equivalence of reflexive and weakly compact
- If $A$ is compact and $B$ is closed, show $d(A,B)$ is achieved
- Combinatorial proofs of the following identities
- Difference between Deformation Retraction and Retraction
- Existence of T-invariant complement of T-invariant subspace when T is diagonalisable
- Advanced beginners textbook on Lie theory from a geometric viewpoint
- the composition of $g \circ f$ is convex on $\Omega$ from Shapley's definition of convexity
- Trace Class: Decomposition
- $f$ is convex function iff Hessian matrix is nonnegative-definite.
- Derivative of the 2-norm of a multivariate function