What is the significance of negative weight edges in a graph?
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.
Asked By : c2h5oh
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14248
Answered By : Subhayan
Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent everything in real world, e.g amount of money to be transferred from one account to another account. The amounts can be positive or negative, then e.g if you want do something, it means you have to go from $a$ to $b$ in your graph with loosing as low as possible money (shortest path), then you can consider a negative weights. For more, see this book chapter.
Apart from that, there are many more. 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. (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$.
In 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 travelling 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.
Post a Comment