|
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.
|
|||||||||||||||||
|
|
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). |
|||||||||||||||||||||
|
|
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). |
|||||||||||||
|
|
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. |
|||||||||
|
|
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...) |
|||
|
|
|
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.) |
|||||||||
|
