60
$\begingroup$

I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.

actually it makes sense that 0 could be used as an edge's weight, but I've been working with graphs in last few days and I have never seen an example of it.

enter image description here

$\endgroup$
  • 28
    $\begingroup$ If negative values are "allowed", then why not a zero? :) $\endgroup$ – Derek 朕會功夫 Jul 28 '16 at 21:09
  • 5
    $\begingroup$ Just as a quick example, if positive weights represent net fuel consumption when travelling from one node to another, then negative weights can represent net refuelling. A zero-weighted edge is where the fuel expended is exactly compensated for by refuelling. $\endgroup$ – J W Jul 29 '16 at 13:27
  • 1
    $\begingroup$ @DavidRicherby I believe the real question here is e.g., "is algorithm X correct in the presence of weight zero edges". Otherwise, what is the context? The answer can be either yes or no, depending on the details. A question like "can an array contain zeros" is just as meaningful. $\endgroup$ – Juho Jul 29 '16 at 17:50
  • 1
    $\begingroup$ @Juho: Oh it's clear all right. It's like asking if a number can be negative. To you it seems obvious that it depends on the context, but it sure wasn't obvious to people until negative numbers came along. Even zero wasn't obvious. $\endgroup$ – Mehrdad Jul 29 '16 at 17:54
  • 1
    $\begingroup$ Depending on what you want to do, your weights might not even be real numbers. For example, if your graph represents an AC circuit, your weights might be phasors, and those are complex numbers. $\endgroup$ – user2357112 supports Monica Jul 30 '16 at 19:13
165
$\begingroup$

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.

The reason you don't usually see zero-weight edges is that, in most contexts, an edge with weight zero is exactly equivalent to the absence of an edge. For example, if your graph represents countries and the amount of trade done between them, a zero-weight edge would mean no trade, which is the same as having no edge at all. If your graph represents distances, a zero-weight edge would correspond to two places at distance zero from each other, which would mean they'd actually be the same place, so should both be represented by the same vertex. However, in other contexts, zero-weight edges could make sense. For example, if your graph represents a road network and edge weights represent the amount of traffic, there's a big difference between a road that nobody uses (zero-weight edge) and no road at all (no edge).

$\endgroup$
  • 1
    $\begingroup$ It's worth noting that many graph algorithms explicitly specify if they work on graphs with negative weights or not. I think this clarifies that even negative weights are allowed, depending on the contexts. $\endgroup$ – Mooing Duck Jul 28 '16 at 20:25
  • 6
    $\begingroup$ @MooingDuck I think the point of the question is that, while algorithms do indeed often say whether or not they work for negative weights, zero weights are rarely mentioned. Negative weights are much less unusual than zero so, in this particular context, I'm not sure they need to be mentioned. $\endgroup$ – David Richerby Jul 28 '16 at 20:52
13
$\begingroup$

It depends on the context. In general yes, edges of zero and even negative weight may be allowed. In some specific cases the edge weights might be required to be non-negative or strictly positive (for instance, Dijkstra's algorithm requires weights to be non-negative).

$\endgroup$
  • $\begingroup$ Is there a specific type of graph that forbids zero? and allows negative or positive values? $\endgroup$ – Taxellool Jul 28 '16 at 10:19
  • 9
    $\begingroup$ "Non-zero edge weighted graph". $\endgroup$ – Tom van der Zanden Jul 28 '16 at 10:31
  • 10
    $\begingroup$ @Taxellool Mathematical objects are not set in stone. There isn't a fixed list of mathematical objects with fixed names that are the only ones you're allowed to use. $\endgroup$ – David Richerby Jul 28 '16 at 11:10
  • $\begingroup$ Depends on which algorithm you use. Bellman-Ford accepts zeros, while in Dijkstra they are obviated $\endgroup$ – Manuel Azar Nov 13 '16 at 18:57
5
$\begingroup$

As the other answers note, you're perfectly free to consider (or exclude from consideration) weighted graphs with zero-weight edges.

That said, in my experience, the usual convention in most applications of weighted graphs is to make no distinction between a zero-weight edge and the absence of an edge. One reason for this is that, typically, weighted graphs show up as generalizations of multigraphs, which in turn are generalizations of simple graphs.

Specifically, a multigraph is a graph that (unlike a simple graph) allows multiple edges between the same pair of nodes. Whereas, in a simple graph, any pair of nodes is always connected by 0 or 1 edges, a pair of nodes in a multigraph may be connected by 0, 1, 2, 3 or more (but always a non-negative integer number of) edges.

Generalizing a multigraph to allow for a fractional number of edges between a pair of nodes then naturally leads one to consider weighted graphs, and many algorithms that work on arbitrary multigraphs can also be made to work on such weighted graphs. But for such algorithms, the "weight" of an edge really denotes its multiplicity. Thus, given this interpretation, there can be no meaningful distinction between "no edge" and "0 edges" between a pair of nodes: both mean exactly the same thing.

Of course, a "weighted graph" by definition is really just a graph with a number associated to each edge, and it's perfectly possible to interpret the weight as something other than multiplicity, in which case a distinction between no edge and a zero-weight edge may indeed be meaningful. But trying to apply standard multigraph algorithms to such "strangely weighted graphs" is unlikely to produce results that would make sense in terms of the alternative (non-multiplicity) interpretation of edge weights.

$\endgroup$
  • 6
    $\begingroup$ How weighted graphs show up "typically" very much depends on your field. When I model a road network as a graph to find shortest paths, the weights represent distances, I don't start with multiple roads between intersections and then introduce fractional roads. $\endgroup$ – adrianN Jul 28 '16 at 15:10
  • 3
    $\begingroup$ @adrianN Though in a graph like that the absence of an edge corresponds to an infinite associated value and not zero. $\endgroup$ – CodesInChaos Jul 28 '16 at 15:47
0
$\begingroup$

Think of a graph of the road system in Cambridge UK, the notes are shared between cyclists and car drivers, so are most of the edges. Doing so greatly decreases the cost of maintaining the data.

Now if we define the edge weight as being travel time in seconds, cleanly each edge will have two weights, one for cars anther for bikes. Some weights will be infinite as cars are not allowed on cycle ways.

Now consider two road junctions that very close to each other so close they are only serrated by a few posts that stop car drivers. (For example a cross road, where car drives can only turn left, but cyclists can go in any direction.) We then get some edges with infinite weight from car drivers and 0 weight for cyclists.

(Clearly the graph could then be pre-processed to create a simpler graph for the routing of cyclists, before working out the best routs.)

$\endgroup$
  • $\begingroup$ I don't see how this addresses the question. The question asks about edges with weight zero. In your example (which, by the way, might not make a whole amount of sense to people not familiar with Cambridge), each edge already has two weights. Now, insofar as you can define weighted graphs however you want, that's fine, but it doesn't seem to be addressing the question asked. Also, the edges you describe all seem to have at least a very small weight for cyclists: even moving a short distance requires a nonzero amount of time. $\endgroup$ – David Richerby Jul 29 '16 at 13:06
  • $\begingroup$ @DavidRicherby, just assume that times of less then 1 second are not recorded. $\endgroup$ – Ian Ringrose Jul 29 '16 at 15:10
0
$\begingroup$

It sounds like you are using the weight to try and represent two distinctly different aspects of the graph. The first is whether the graph actually has a representable (drawn) edge, and the second is it's actual weight.

As you have noticed, you drop into a confusing situation if you have used 'non-zero' as an indicator that an edge is present (and would need to be drawn, or listed), while at the same time have now found a situation where zero weight is classed as valid.

Essentially you will need another way of representing the presence of the edge (assuming you actually need that, and can't simply create an N^2 array of weights, but then you fall into the trap of needing to decide what to do about loop back edges...)

$\endgroup$
  • $\begingroup$ I'm not sure this really answers the question. The question is about whether graphs might have zero-weight edges; your answer is mostly about how one might implement a data structure for graphs with zero-weight edges. $\endgroup$ – David Richerby Jul 30 '16 at 9:30
  • $\begingroup$ @DavidRicherby, Close; It (my answer) was more about why and how the question came (or may have come) into being - An XYProplem issue. Often being able to rationalise about why it was an issue in the first place can help greatly in seeing how the solution is the right answer and not just some 'fudge' $\endgroup$ – Philip Oakley Jul 30 '16 at 16:04

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.