2
$\begingroup$

I am sorry my English is not very good. my problem might look simple for everyone here. I have read about Floyd–Warshall algorithm in wikipedia,every thing was good but when I start reading "Behavior with negative cycles" I face problem in understanding this sentence: "There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to j can be arbitrarily small (negative)" I don't understand what it exactly mean. can anyone help me please. Behavior with negative cycles

$\endgroup$
3
$\begingroup$

Given a graph, suppose to have a cycle given by Nodes $i \ $,$\ j$,$\ k$ of negative cost.

Example:

  • $w(i,j)=2,\ w(j,k)=4,\ w(k,i)-7$

    +---+    +2      +---+
    | i |+---------->| j |
    +-+-+            +-+-+
      ^                |
      | -7             |+4
      |     +---+      |
      +----+| k |<-----+
            +---+
    

Suppose you want to find the shortest path between $i$ and $j$.

You have

$P=\{(i,j)\}$ with $cost(P)=2$

but you can loop through the negative cycle and have:

$P'=\{(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P')=1$ $P''=\{(i,j),(j,k),(k,i),(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P'')=0$ and so on.

You could loop forever through the negative cycle and decrease the cost of the path.

Same if you consider an undirected graph with an edge that has negative weight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.