Questions tagged [weighted-graphs]

Questions about graphs in which every edge is associated with a weight.

Filter by
Sorted by
Tagged with
60
votes
5answers
10k views

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

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, ...
42
votes
3answers
40k views

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

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
22
votes
3answers
17k views

When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
21
votes
2answers
8k views

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

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
14
votes
2answers
2k views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
11
votes
0answers
511 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
10
votes
3answers
9k views

Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
10
votes
0answers
207 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
9
votes
2answers
3k views

What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
9
votes
1answer
2k views

Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights

I ran into the following problem: Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut. For general graphs this is NP-hard, since one ...
7
votes
2answers
5k views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
7
votes
2answers
12k views

Shortest path that passes through specific node(s)

I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
6
votes
2answers
696 views

An edge that connects more than two nodes in a graph?

Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
6
votes
2answers
1k views

Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
6
votes
2answers
588 views

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example. What I am trying to achieve with one sentence How can I answer the ...
6
votes
2answers
197 views

Path in an edge-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....
5
votes
3answers
453 views

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

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally: Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such ...
5
votes
1answer
1k views

Finding shortest paths in undirected graphs with possibly negative edge weights

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge ...
5
votes
2answers
1k views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
5
votes
1answer
1k views

Konig's Theorem for Min Weight Vertex Cover?

Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover. Wikipedia states that there is an equivalent version of the ...
5
votes
1answer
45 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+...
5
votes
1answer
4k views

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

I need your help with an exercise on Ford-Fulkerson. Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance. Now suppose you are ...
5
votes
1answer
652 views

Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
5
votes
0answers
543 views

Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes). The nodes each side are both (at ...
4
votes
2answers
619 views

Diameter-constrained Minimum Spanning Tree Problem

The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of ...
4
votes
1answer
5k views

A* to find the longest path in a directed cyclic graph

I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph. My attempt was to write it so that ...
4
votes
1answer
961 views

All pairwise shortest paths in a graph: does knowing the path weights help?

This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we ...
4
votes
2answers
344 views

Complexity of shortest paths if paths have to use edges from different partitions

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully ...
4
votes
1answer
61 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
4
votes
1answer
130 views

Path cover with paths of bounded length, in the plane

I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the ...
4
votes
0answers
349 views

graph signal processing

What's the intuition behind a ''Graph fourier transform'' ? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a graph fourier transform actually ...
4
votes
0answers
353 views

Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
3
votes
2answers
277 views

Weight functions in graph algorithms

In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$. Why ...
3
votes
1answer
5k views

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

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not ...
3
votes
2answers
137 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
3
votes
1answer
1k views

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

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
3
votes
2answers
8k views

Dijkstra's algorithm for edge weights in range 0, …, W

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes ...
3
votes
1answer
511 views

Multiple Source Shortest Paths in a weighted graph

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
3
votes
1answer
146 views

Maximal Minimum Spanning Tree by Removing $k$ Edges

The problem is as follows: Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove ...
3
votes
2answers
606 views

Girth of Undirected Graph with Positive Integer Weights

Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e. $g(G) := \...
3
votes
1answer
81 views

Finding minimum spanning tree of a special form graph

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ...
3
votes
1answer
461 views

Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
3
votes
1answer
2k views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
3
votes
1answer
62 views

Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
3
votes
1answer
135 views

Constructing a minimum spanning tree from an all-shortest path graph?

Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a ...
3
votes
1answer
92 views

Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$. Is this problem NP-hard? I thought ...
3
votes
1answer
4k views

maximum weighted path(s) in a DAG

Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current ...
3
votes
1answer
329 views

Finding path that minimizes largest of the sum of weights of each group in a directed multigraph

Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group? All weights are non-negative integers in ...
3
votes
3answers
858 views

Path in directed, weighted, cyclic graph with total distance closest to D?

Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d. Output: A path between A and B with distance closest to d....
3
votes
1answer
110 views

Seemingly non sequitur in proof

I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument. ...