A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [weighted-graphs]

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

217 questions
Filter by
Sorted by
Tagged with
634 views

### Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
44k 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 ...
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 ...
1k views

### Calculating the number of non-intersecting routes in an Euclidean graph

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that every optimal TSP solution ...
354 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 ...
4k views

### Efficient way to find intersections

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am randomly creating a path thru all the vertices and I ...
192 views

### Converting graphs to sets of paths

I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. The number of vertices with no edges is small ...
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 ...
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 ...
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 ...
658 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 ...
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 ...
147 views

### Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
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 ...
3k 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 ...
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 ...