# Tag Info

166

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

42

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality). If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a ...

34

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 into account when predicting range. In a neural network, we can use negative weights to indicate that one neuron firing is inversely correlated with another ...

23

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 does not create cycles, include it in the MST Two edges cannot construct a cycle in a simple graph By the correctness of Kruskal’s algorithm, the two ...

23

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 road network. If you want to find a path from A to B in a road network, you need to keep all the road segments that exist. There are two important measures: ...

13

A path of length $n$ consists of $n$ line segments in the plane. You want to find all intersections between these line segments. This is a standard problem that has been studied in depth in the computer graphics literature. A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric ...

13

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 trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this ...

13

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$. If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest ...

13

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

12

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 with only a few edges. For a simple case, consider the graph with vertices $\{a,b,c\}$ and edges $\{ab,bc,ac\}$, where $ab$ and $bc$ have length $1$ ...

12

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 control civilian and military units over this map. Each unit has a specific allocation of movement points, and each terrain type costs a specific amount of movement ...

11

It is NP-complete to even decide whether any path exists. It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem. Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem: ...

10

There are exponentially many such routes. Think of a sequence of $n$ diamonds. At each diamond, you can go either left or right, independently of what you do at all other diamonds. This leads to $2^n$ paths, each of which is non-intersecting. Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on ...

10

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$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or ...

8

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. For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of ...

8

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

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 have multiple devices connected to a single wire, we can treat that as separate vertices with 0 weight nodes between them. We can transform them into one "...

7

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 automaton with a weight function on the edges (or states). Then, a run is assigned a weight according to the weight it traverses. There are many different semantics ...

7

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 highlighted in red) is minimum. Its total cost is 7 and the diameter is equal to 5. In contrast, the spanning tree on the right is not minimum (since its total cost ...

7

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$ becomes a pair of vertices $v_+, v_-$ connected by an edge in $G'$. All of these edges should also be added to $F$. Then for each $(u, v) \in E$, add the ...

7

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 found the following two lecture notes: Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest ...

7

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 pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...

7

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 Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...

7

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 of the sentiment. In quantitative finance where the nodes are securities and the connections are the correlation coefficients. A few years ago I made a ...

6

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 partition $P$ of nodes $V = \{1,2,\dotsc,N\}$. Maintain a tree $T$. We will maintain the invariant that $T$ contains some edges of the tree that we are trying to ...

6

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{ is edges of a path from } s \text{ to } v \}$ i.e. the shortest path between $s$ and $v$. Let's prove by induction on the step of Dijkstra's algorithm that ...

5

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. Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$. The problem is para-NP-hard in the unweighted case and the problem is just ...

5

First of all, bear in mind that the Longest Path Problem (LPP) is a NP-complete problem whereas finding the Shortest Path Problem (SPP) is a problem known to be in P. The proof for the NP-completeness of LPP is trivial and consists of a reduction from the Hamiltonian Circuit (HC) problem which is already known to be NP-complete. In other words, if you could ...

5

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 function $w$ takes on values in $[m]$, so we have a partition of $E$ into sets $E_i := w^{-1}(i)$ for $i\in [m]$. We can do induction on the number $j$ of non-...

5

Introduction This answer is in two parts. The first is an analysis of the problem mixed with a sketch of the algorithm to solve it. As it is my first version, it is detailed, but results in an algorithm that is a bit more complex than needed. It is followed by a pseudo-code version of the algorithm, written sometime later, as the algorithm was clearer. ...

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