167 votes
Accepted

Is zero allowed as an edge's weight, in a weighted graph?

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 ...
34 votes

Real life examples of negative weight edges in graphs

Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that ...
  • 13.6k
24 votes

Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
  • 13.6k
23 votes

Does the Minimum Spanning Tree include the TWO lowest cost edges?

For simple graphs*, it is true for the following reason: Kruskal’s algorithm is correct Kruskal’s algorithm works as follows: sort the edges by increasing weight repeat: pop the cheapest edge, if it ...
  • 13.6k
13 votes
Accepted

Why do we have different algorithm for MST when graphs are directed?

Your question was already asked before it seems, but got no explicit examples. I try to give these here. First note the question only makes sense if we consider a node $u$, and there exist spanning ...
  • 28.5k
13 votes
Accepted

When is the minimum spanning tree for a graph not unique

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2. Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$. ...
  • 558
13 votes

Is zero allowed as an edge's weight, in a weighted graph?

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 ...
12 votes

Why does Dijkstra's algorithm fail on a negative weighted graphs?

Adding a constant amount to each edge length can change the shortest path for the simple reason that it increases the length of a path with many edges by more than it increases the length of a path ...
12 votes

Real life examples of *zero* weight edges in graphs

The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players ...
  • 1,072
10 votes
Accepted

What are Markov chains?

A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ ...
9 votes

Real life examples of *zero* weight edges in graphs

In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we ...
  • 3,223
8 votes

What are Markov chains?

Markov Chains come in two flavors: continuous time and discrete time. Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs. ...
  • 81
8 votes

Diameter-constrained Minimum Spanning Tree Problem

Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.
8 votes

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted ...
7 votes

What is a weighted or probabilistic automaton?

The setting you suggest is not clear enough to determine what kind of an automaton you are looking for. A short explanation regarding the types of automata: A weighted automaton is typically an ...
  • 16.6k
7 votes
Accepted

Diameter-constrained Minimum Spanning Tree Problem

There is no direct relationship between the diameter of a (minimum) spanning tree and the total cost of the tree1. Consider the following example: The spanning tree on the left (whose edges are ...
7 votes
Accepted

Shortest walk through a given subset of edges

This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists. Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ ...
7 votes
Accepted

Finding shortest paths in undirected graphs with possibly negative edge weights

I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint: Try adding "t-joins" or "perfect matching" to your web searches. Following this, I ...
  • 9,289
7 votes
Accepted

Weight functions in graph algorithms

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is ...
  • 35.8k
7 votes
Accepted

Dijkstra with max instead of sum

Yes, it is true. Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{...
7 votes

Real life examples of negative weight edges in graphs

In a social network. Where the source node is a person the target node is another person and the connection represents the preference the source has for the target. The sign representing the direction ...
  • 91
6 votes
Accepted

Is it possible to reconstruct graph if we have given matrix of shortest pairs

I would suggest the following approach. Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$. Maintain a ...
5 votes

Covering a graph with non-overlapping cliques

Thus I'm still curious if there are other more efficient approaches to solving the problem. If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem. ...
  • 13.6k
5 votes

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

Here is a slightly simpler argument that also works for other matroids. (I saw this question from another one.) Suppose that $G$ has $m$ edges. Without loss of generality, assume that the weight ...
  • 2,896
5 votes
Accepted

Dijkstra's algorithm to compute shortest paths using k edges?

If the graph has no negative edges, the problem can be solved in $O(k \cdot (|V|+|E|) \lg |E|)$ time using Dijkstra's algorithm combined with a product construction. We construct a new graph $G'=(V',...
  • 146k
5 votes

When is the minimum spanning tree for a graph not unique

A previous answer indicates an algorithm to determine whether there are multiple MSTs, which, for each edge $e$ not in $G$, find the cycle created by adding $e$ to a precomputed MST and check if $e$ ...
  • 35.8k
5 votes

Is zero allowed as an edge's weight, in a weighted graph?

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 ...
5 votes
Accepted

Multiple Source Shortest Paths in a weighted graph

Yes. Here is the trick that always works: create a new source, $s_0$, and add an edge (with length 0) from $s_0$ to each of your starting vertices. Then, run any shortest-paths algorithm starting ...
  • 146k
5 votes
Accepted

Uniqueness of minimum spanning tree

If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.
5 votes

Weight functions in graph algorithms

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has ...
  • 2,977

Only top scored, non community-wiki answers of a minimum length are eligible