165 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 ...
David Richerby's user avatar
35 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 ...
Pål GD's user avatar
  • 15.9k
25 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 ...
Pål GD's user avatar
  • 15.9k
24 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 ...
Pål GD's user avatar
  • 15.9k
14 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 ...
David Richerby's user avatar
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 ...
Hendrik Jan's user avatar
  • 30.5k
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 ...
Tom van der Zanden's user avatar
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$. ...
dtt's user avatar
  • 558
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 ...
kviiri's user avatar
  • 1,227
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 ...
Cort Ammon's user avatar
  • 3,351
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$.
Yuval Filmus's user avatar
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 ...
David Richerby's user avatar
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 ...
Mario Cervera's user avatar
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$ ...
j_random_hacker's user avatar
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 ...
hengxin's user avatar
  • 9,541
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 ...
John L.'s user avatar
  • 38.9k
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{...
Artur Riazanov's user avatar
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 ...
stam_a's user avatar
  • 91
6 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$ ...
John L.'s user avatar
  • 38.9k
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 ...
Jukka Suomela's user avatar
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 ...
Ilmari Karonen's user avatar
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',...
D.W.'s user avatar
  • 159k
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 ...
D.W.'s user avatar
  • 159k
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.
David Richerby's user avatar
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 ...
HEKTO's user avatar
  • 3,088
5 votes
Accepted

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

The MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that: Claim 1: either all MSTs use only edges with integer weights or none of them does. ...
Steven's user avatar
  • 29.4k
5 votes
Accepted

Efficiently determine which nodes should leave a graph while maintaining connectedness

The problem is equivalent to the node-weighted version of the Steiner tree problem. Happy nodes correspond to terminals, and non-removed unhappy nodes correspond to Steiner vertices. This problem is ...
pcpthm's user avatar
  • 2,339
4 votes

When is the minimum spanning tree for a graph not unique

Let $G$ be a (simple finite) edged-weighted undirected connected graph with at least two vertices. Let ST mean spanning tree and MST mean minimum spanning tree. Let me define some less common terms ...
John L.'s user avatar
  • 38.9k
4 votes

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

Actually , Dijkstra's algorithm fails to work for most of the negative weight edged graphs , but sometimes it works with some of the graphs with negative weighted edges too provided the graph doesn't ...
jeshwanth chowdary's user avatar
4 votes

Effect of increasing the capacity of an edge in a flow network with known max flow

I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f_e$ is the flow on edge $e$. I am also assuming that all the capacities and flows ...
foo's user avatar
  • 41

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