New answers tagged


When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.


Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists). To prove this, we can use induction: ...


The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree. Let's call $T$ the solution for the input graph $G$. Let's also call $T_i$ the solution for the problem $G_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I ...


My current strategy is: first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library. sum all the weights of edges in each cycle and then check if the sum is negative.


As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).

Top 50 recent answers are included