# Questions tagged [weighted-graphs]

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

229 questions
Filter by
Sorted by
Tagged with
410 views

### Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
355 views

### Can I change the order of iteratorion in the Floyd-Warshall Algorithm?

I am studying how Floyd-Warshall works and came across this doubt. In the code: ...
913 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....
225 views

### Vehicle Routing Problem Using Simulated Annealing

Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely ...
1k views

### Does Dijkstra's Algorithm actually check nodes marked as visited?

I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works. So, most ways the algorithm has been explained to me involve going from a source ...
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, ...
592 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 ...
20k 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 ...
78 views

### I know the algorithms, but i still don't know how to approach the questions

I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new ...
840 views

### Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
214 views

### Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous ...
171 views

### Maximum weighted antichain over a DAG with cardinality constraint

Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights. Let also $k\leq \left\vert V\right\vert$, is there any way to find a maximum weighted antichain ...
321 views

### Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the cycle ...
546 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 ...
1k views

### Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

Let's say for the following weighted, undirected graph: I am given the adjacency matrix A[5][5]: ...
88 views

### Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
494 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 ...
6k 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 ...
46 views

2k 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$ ...
236 views

### Edge-connectivity of a weighted undirected graph

My question consists of two parts. Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so? My guess: ...
993 views

### Generate random weighted graphs representing a road network

in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current ...
255 views

### What is a weighted or probabilistic automaton?

I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank). Therefore, I'm looking to implement an automaton, ...
86 views

### Branch clustering for an MST

I am working in image segmentation with super pixels. My data is a large matrix describing various attributes of each stick of pixels (such as height, width and disparity). The data comes from an ...
1k 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 ...
707 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 ...
316 views

### Directed cyclic graph with node rewards and arc costs

The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain ...
208 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 ...
714 views

### Improve minimum spanning tree with new edge, with better running time than O(|V|)?

The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ ...
413 views

23 views

### Finding next lightest path [duplicate]

Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The ...
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. ...
2k views

### Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
1k views

### Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

I have been scratching my head to find good counter examples to the following problem: Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A ...