0
$\begingroup$

I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to carry a negative weight, and be represented as a positive number?

As an example, suppose we had a graph of a network where the edges represent the time elapsed for data to travel between server A and server B. Suppose that we had a weight on each edge representing the lag time between certain servers (so perhaps the time for the data to travel between A and B has a lag of time t, which means the total time can be shown as the time to get to B from A, plus the lag). Is "lag" a negative edge weight in this case, even though it is a positive number?

$\endgroup$
6
  • 2
    $\begingroup$ You are free to interpret your weights exactly how you feel like. $\endgroup$
    – Pål GD
    Jun 11, 2023 at 19:47
  • $\begingroup$ Why would you see that lag as a negative weight ? And what is the meaning of "the time to get to B from A" vs. "the lag" ? Aren't they the same thing ? $\endgroup$
    – user16034
    Jun 12, 2023 at 10:04
  • $\begingroup$ @PålGD: are you free to say that -1 is a positive number ? $\endgroup$
    – user16034
    Jun 13, 2023 at 18:16
  • $\begingroup$ @YvesDaoust I consider -1 a very positive number. Much more positive than for example -2. I also think of 1 as a much more negative number than other numbers such as 2. $\endgroup$
    – Pål GD
    Jun 14, 2023 at 7:56
  • $\begingroup$ @PålGD: one says 'larger' and 'smaller', not 'more positive'/'more negative'. And "more positive" does not coincide with "positive". -1 being "very positive" is absurd. In fact, -1 is red and -2 is redder. $\endgroup$
    – user16034
    Jun 14, 2023 at 8:15

2 Answers 2

2
$\begingroup$

Short answer:

A positive weight is a positive number. A negative weight is a negative number.

$\endgroup$
0
$\begingroup$

The negative and positive refers to the sign of the number, i.e., a negative weight = negative number.

The reason why negative weights are important is because many algorithms only work when the edge weights are a non-negative.

A simple example of an algorithm is Dijkstra's Algorithm to find shortest paths in a graph. It doesn't work on graphs with negative weight. An example of such a graph is the following (if Dijkstra is run starting at node $a$):

enter image description here

In the example you gave above, intuitively it seems that lag time should be a positive number (since you'd want to minimise it), but it depends on the application, and I suppose both representations should work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.