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
39 views

### Is a spanning tree an MST if its weight can't be decreased by adding an edge and removing one? [duplicate]

My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges ...
684 views

### Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
296 views

### Longest path in a DAG: source to sink?

Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index ...
440 views

### Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
66 views

### Understanding characterizations of Matching on Graphs

I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right. Definition: Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching ...
702 views

### Single pair shortest path algorithm with time a constraint

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional ...
194 views

### Find minimum time path between two nodes

I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers. A graph with Vertices representing charges and Edges representing distances ...
124 views

### Algorithm to calculate average weight from every pair of nodes [duplicate]

I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph. For example, for the following graph: The results is calculated like this: 1 -> 2 = 3; 1 -...