Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
375
questions
1
vote
1
answer
60
views
Can Dijkstra's algorithm be used this way?
Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
CommunityBot
- 1
0
votes
1
answer
201
views
Total weight of Huffman Code
We are given the following letters with the respective frequencies:
\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
0
votes
1
answer
116
views
How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?
How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
CommunityBot
- 1
0
votes
2
answers
68
views
MInimum Spanning Tree and Combinatorics
I just got a small confusion here,
I have a graph for which i need to get number of minimum spanning tree,
So, in graph i have 3 edges with weight 2 and 4 edges with weight 3,
in such a way that AE = ...
CommunityBot
- 1
0
votes
0
answers
14
views
Prove that the a bottleneck of path P is maximal
As the title says, the question is about finding the maximal bottleneck edge in path P.
Bottleneck of a path P in an undirected graph G = (V,E) is defined to be the weight of the edge with minimal ...
- 11
0
votes
2
answers
102
views
Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST
In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor:
Let $T$ be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
- 654
1
vote
1
answer
307
views
A pathfinding algorithm for graphs in which arc weights can change over time
So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.
Here's the situation, I have a weighted undirected ...
CommunityBot
- 1
1
vote
1
answer
68
views
Finding min s-t cut of network with flow on the nodes
Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes?
We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
CommunityBot
- 1
0
votes
0
answers
58
views
Find an independent set in which the cumulative sum of weights is maximized
I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
D.W.♦
- 159k
0
votes
1
answer
91
views
Transforming a Travelling Salesman Problem to a Maximum Clique Problem
Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
CommunityBot
- 1
2
votes
1
answer
406
views
A more rigorous proof on a Bellman-Ford's corollary
The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"
Corollary 24.3
Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$
and a ...
CommunityBot
- 1
1
vote
0
answers
17
views
Finding optimal threshold using small world network metrics to binarize 2 groups for comparison
I have two groups (GROUP1 and GROUP2) of undirected weighted graphs - one having properties more similar to small world network and other relatively random. These are represented as adjacency matrices ...
2
votes
1
answer
56
views
Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?
Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
- 6,157
1
vote
1
answer
204
views
Find a weight threshold for edges for maximum number of connected components in a graph
So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
CommunityBot
- 1
4
votes
0
answers
146
views
Negative cycle of even length
Given an undirected graph $(V,E)$ with weights on edges $\in Z$ is it possible to find a negative cycle of even length (not the weight of the cycle, but the number of edges contained in the cycle) in ...
- 41
2
votes
1
answer
99
views
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
The rural postman problem is:
Given a weighted MultiDiGraph $G=(V,E)$, a subset of ...
CommunityBot
- 1
2
votes
1
answer
211
views
Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
...
CommunityBot
- 1
2
votes
1
answer
2k
views
Updating a mst after increasing the weight of an edge in the mst
Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$
Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$.
I'm using a common ...
CommunityBot
- 1
1
vote
1
answer
177
views
Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?
Furthermore, say we are doing many ...
CommunityBot
- 1
1
vote
1
answer
78
views
Running time of modified BFS algorithm to find shortest path in weighted DAG
While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
D.W.♦
- 159k
0
votes
0
answers
28
views
Distance to specific node incremental addition
Let us say I have an empty graph G and a list of nodes N to add to the graph one-by-one. Let us say that I will have a node <...
- 101
1
vote
1
answer
25
views
Graph Algorithms (SSSP vs MST)
I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to ...
CommunityBot
- 1
1
vote
1
answer
80
views
number of edges that appeared at least in one shortest path
In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices.
...
- 13
0
votes
1
answer
179
views
Shortest Hamiltonian Path in a Complete Graph
I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm ...
- 837
0
votes
2
answers
448
views
Calculate shortest cycle that contains node $s$
Let $ G(V, E, w)$ be a graph with no negative weights.
Describe an algorithm that returns the shortest cycle containing a node $ v $.
I came across this algorithm https://courses.engr.illinois.edu/...
D.W.♦
- 159k
1
vote
1
answer
29
views
Algorithm for constructing a numbering reflecting the order of activities
I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) ...
D.W.♦
- 159k
0
votes
1
answer
61
views
How to modify Dijkstra's algorithm to model the path of an electric car?
I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks.
Somebody online asked (but nobody ...
- 30.6k
1
vote
0
answers
309
views
Clash Royale Algorithm for troops path
I am making a clone of Clash Royale which is basically a Tower Defence game.
As you can see from the picture you can deploy different troops only in your side of the court (that blue rectangle), and ...
0
votes
1
answer
105
views
find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)
We have a weighted and undirected graph.
I want to find the shortest path between two vertices with Dijkstra algorithm.
But in the path, the weight of the edges should be increased and decreased one ...
CommunityBot
- 1
0
votes
0
answers
39
views
Running time of variant of Dijkstra's algorithm
Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
- 286
1
vote
1
answer
62
views
Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
- 29.5k
1
vote
0
answers
59
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
1
vote
0
answers
26
views
What is the name of this extension of the maximum independent set problem?
Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
3
votes
1
answer
144
views
Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
- 121
4
votes
2
answers
225
views
Single Source Shortest Path Problem with Multiple Weights Each Edge
I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
D.W.♦
- 159k
0
votes
2
answers
68
views
Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
0
votes
1
answer
116
views
How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford
I want to find how many shortest paths are there from Node A to node B.
For example, let's say we have a graph with 3 nodes and 3 connections:
from 1 to 2 weight 5
from 1 to 3 weight 11
from 2 to 3 ...
CommunityBot
- 1
1
vote
2
answers
1k
views
What is the graphic TSP?
I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :
...graph-TSP, that is, the traveling salesman problem where distances ...
0
votes
0
answers
20
views
Solving a weighted minimum dominating set problem with its unweighted counterpart?
Question
Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set?
Elaboration
In essence, can one convert a ...
- 123
1
vote
0
answers
106
views
Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line
Consider a DAG such as one shown below:
How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
- 280
0
votes
1
answer
41
views
Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
- 29.5k
0
votes
1
answer
89
views
Directed weighted multigraph with dynamic edges - shortest path
I need to create an implementation of a directed weighted multigraph with dynamic edges:
The edges will be changing during the pathfinding, in the following way:
Summary of the pathfinding:
...
- 529
0
votes
1
answer
322
views
Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time
The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
- 11
1
vote
1
answer
354
views
Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph
I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest".
I thing that the claim may be false (i.e there might ...
- 39k
3
votes
3
answers
506
views
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Traditionally, the traveling salesman problem has you visit a city at least once and at most once.
However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
- 30k
0
votes
1
answer
96
views
How sparsity term in loss function for sparse autoencoder is making hidden units inactive?
I am working on a Sparse Autoencoder but Andrew NG's notes are hard to understand.
My question is about the following equation: Loss Function.
In sparse autoencoder, the goal is to inactive some ...
D.W.♦
- 159k
-1
votes
1
answer
654
views
How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
- 15.5k
2
votes
1
answer
661
views
Detecting cycles with weight zero in a directed graph
I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles.
I need to find an algorithm that returns ...
CommunityBot
- 1
1
vote
3
answers
176
views
Algorithm to find Minimal Spanning Subgraph
I'm attempting to solve this problem:
Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')...
- 71
1
vote
2
answers
76
views
Shortest path algorithm on graphs with non-numerical weights
TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
