# Floyd–Warshall algorithm ,Behavior with negative cycles

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

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.