13
$\begingroup$

I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.

So, I wonder what's the real world significance of negative weight edges? A plain English explanation would be helpful.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Weight of edges can represent everything in real world, e.g amount of money to be transferred from one account to another account can be positive or negative, then e.g if you want do something means you have to go from a->b in your graph with loosing as low as possible money (shortest path), then you can consider a negative weights .... e.g see this book chapter which contains some samples: informit.com/articles/article.aspx?p=169575&seqNum=8 $\endgroup$ – user742 Sep 10 '13 at 15:27
  • $\begingroup$ so if a ----(2)----> b ----(-2)----> c and a-----(1)----> c and to go from a to c,should I choose path a-b-c as total cost is 0 ? because it's shortest path. correct me if i am wrong ! $\endgroup$ – c2h5oh Sep 10 '13 at 15:33
  • $\begingroup$ e.g suppose if you doing job $e(ab)$ to going from state $a$ to $b$ costs $2\$$ (e.g job is buying book costs 2$\$$), after that you can do some project (you earn 2$\$$, means cost function is -2), then you achieved your purpose (being professional or c), then total cost is 0, and you are in your state. a--(+2)-->b--(-2)-->c : +2 - 2 = 0 (total cost from a: newbie, to c: professional). $\endgroup$ – user742 Sep 10 '13 at 15:39
  • $\begingroup$ so my assumption is right , even if we have to travel 1 more edge we'll choose a-b-c instead of a-c.am I right? $\endgroup$ – c2h5oh Sep 10 '13 at 15:42
  • $\begingroup$ Yes exactly, your assumption is right. Note that you can read some more (like the link I provided for you) or by our discussion you can answer your own question, and mark it as accepted answer. $\endgroup$ – user742 Sep 10 '13 at 16:27
14
$\begingroup$

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

enter image description here

  • Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Modes: compounds, edge $e_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$. In this graph: you produce $4$ kJ to convert $s-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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hi, Thanks for the answer. Can someone explain the rock-paper-scissor example? How did you come up with weights 4, 2, -5 for them? $\endgroup$ – Saurabh Goyal Apr 13 at 11:57
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

enter image description here

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.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ I don't think this answers the question. The question is not "why is a negative cycle a problem", but rather "why would one ever have edges with negative weights in real life". $\endgroup$ – Juho Sep 10 '13 at 18:28
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Welcome to the site! I don't think this is a very good example. In the case of traffic congestion, it seems more natural to weight edges on the map by the time it takes to travel along the road, so high congestion would lead to high weight. After all, the aim is usually to get to the destination quickly and one would usually prefer to take a short but congested road rather than a much longer uncongested road. Also, we typically want to use least cost as the metric: that works well with the weighting I suggested, and very badly with the one that you suggested. $\endgroup$ – David Richerby Mar 24 '18 at 18:30

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.