# Tag Info

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 ...
• 80.7k

### 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

### 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

### 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
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
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

### 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 ...
• 13.1k

### 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 ...
• 80.7k

### 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
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$ ...
• 17.4k

### 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

### 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

### 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$.
• 272k

### 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 ...
• 80.7k

### 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
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 ...
• 3,544
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$ ...
• 5,194
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
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
Accepted

• 146k

### 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

### 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 ...
• 2,055
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
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.
• 80.7k