HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
significancetheedgesgraphwhatweightnegative

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#14248, answer score: 21

Revisions (0)

No revisions yet.