What is the significance of negative weight edges in a graph?

For example, imagine a logistic network where the weight w(i,j) of an edge ij is the cost to go from vertex i to vertex j. If you made a business agreement with other companies to transport their products, w(i,j) would be a profit instead of a cost, so you can interpret this weight as a negative cost.

Traffic congestion on a map:

One other real world example of associating weights to an edge could be the weights represent traffic conditions in a map (more negative, more unfavorable) - we could then use this representation to compute optimal distances.

We can really use the "weight" metaphor to represent anything of positive/negative value between any two points in a graph

I am not a chemistry guy but still I think this example will be worth to help you think out of processor , network theory and related stuff ..

Consider a graph simulating behavior of a molecule in a chemical reaction ie which paths it can take during reaction and weights represents energy absorbed or released in the transition, so if we want energy out of the reaction we represent released energy with +ve weights and absorbed energy with -ve.

Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (shortest path), then you can consider negative weights. For more, see this book chapter.

Apart from that, there are many more applications. The negative weights depend on what you model it to be. For example, consider this graph

• Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Nodes: compounds, Edge $e_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$). In this graph: you produce $4$ kJ to convert $s$ to $a$ and $2$ kJ to convert $a$ to $t$. You need $5$ kJ to get back $s$ from $t$.

• Real Life: Think of a driver, who gets paid to drive his employer from $s$ to $t$ but he pays between $a$ and $b$ (say traveling between his home and his workplace).

• Games: Suppose you play rock-paper scissor for money. Nodes: rock, paper, scissors. Edges: any relation (clique). Weights: wager. In this graph: (forget about $b$), here, $s$ beats $a$, $a$ beats $t$ and $t$ beats $s$, and wins 4,2,-5 respectively.

A negative edge is simply an edge having a negative weight. It could be in any context pertaining to the graph and what are its edges referring to. For example, the edge C-D in the above graph is a negative edge. Floyd-Warshall works by minimizing the weight between every pair of the graph, if possible. So, for a negative weight you could simply perform the calculation as you would have done for positive weight edges.

The problem arises when there is a negative cycle. Take a look at the above graph. And ask yourself the question - what is the shortest path between A and E? You might at first feel as if its ABCE costing 6 ( 2+1+3 ). But actually, taking a deeper look, you would observe a negative cycle, which is BCD. The weight of BCD is 1+(-4)+2 = (-1). While traversing from A to E, i could keep cycling around inside BCD to reduce my cost by 1 each time. Like, the path A(BCD)BCE costs 5 (2+(-1)+1+3). Now repeating the cycle infinite times would keep reducing the cost by 1 each time. I could achieve a negative infinite shortest path between A and E.

The problem is evident for any negative cycle in a graph. Hence, whenever a negative cycle is present, the minimum weight is not defined or is negative infinity, thus Floyd-Warshall cannot work in such a case.

As an addition, you might want to take a look at Bellman-Ford Algorithm which detects whether a graph have negative cycle or not and otherwise return the shortest path between two nodes.