Suggest an edit

Improve this article

Refine the answer for “What is a weighted graph?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A weighted graph is a graph in which each edge (sometimes each vertex) is assigned a numeric value, a weight. The weight usually represents cost, distance, time, bandwidth, or probability, and is used when computing paths, spanning trees, and other graph characteristics.

## Detailed answer

### Formal definition

A weighted graph is a triple G = (V, E, w), where V is the set of vertices, E is the set of edges (ordered for a directed graph and unordered for an undirected one), and w is the weight function. Most often w assigns weights to edges: w: E → R (real numbers). Sometimes weights are used on vertices instead: w: V → R, or on both vertices and edges at once.

- Directed and undirected: weighting applies in both cases.
- Weight range: weights can be positive, zero, or negative (depending on the problem and the algorithm).
- An unweighted graph is a special case where every weight equals 1 (or some other identical constant).

### Why weights are needed (interpretations)

- Cost: the price of traversing an edge (for example, a tariff or resource expenditure).
- Distance/time/delay: the length of a road, delivery time, latency between network nodes.
- Bandwidth/reliability/probability: connection quality metrics.

### Key properties and nuances

- The length of a path is the sum of its edge weights (or a combined sum if vertex weights are also counted).
- Negative edges are allowed, but negative cycles make the shortest-path problem ill-defined (no minimal length exists).
- In minimum spanning tree (MST) problems the weights are usually on the edges; negative weights are possible too, the algorithms still find the spanning tree of minimal total cost.
- A vertex weight can be reduced to edge weights, for example by splitting the vertex into an in-node and an out-node connected by an edge that carries the vertex's weight.

### In-memory representations

- Adjacency lists: each vertex stores a list of (neighbor, weight) pairs. Memory-efficient for sparse graphs.
- Adjacency matrix: a square matrix where cell i,j is the weight of edge i→j, and a missing edge is encoded with a special value (for example, Infinity). Convenient for dense graphs.

```
// Example: adjacency list with weights
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 2 }],
  B: [{ to: 'C', w: 5 }, { to: 'D', w: 10 }],
  C: [{ to: 'E', w: 3 }],
  D: [{ to: 'F', w: 11 }],
  E: [{ to: 'D', w: 4 }],
  F: []
};

// Example: adjacency matrix (Infinity means a missing edge)
const V = ['A', 'B', 'C'];
const INF = Infinity;
const M = [
  /*A*/ [0,    7,    2   ],
  /*B*/ [7,    0,    INF ],
  /*C*/ [2,    INF,  0   ]
];
```

### Basic algorithms for weighted graphs

1. Single-source shortest paths: Dijkstra (non-negative weights only).
2. Shortest paths with possible negative edges: Bellman-Ford; for a DAG, dynamic programming over the topological order (allows negative edges as long as there are no cycles).
3. All-pairs shortest paths: Floyd-Warshall (suitable for small graphs, O(V^3)) or Johnson's algorithm (more efficient on sparse graphs).
4. Heuristic search: A* (requires an admissible heuristic, non-negative weights).
5. Minimum spanning tree: Kruskal's, Prim's (work with any edge weights, including negative ones).

### Example: shortest path (Dijkstra, JavaScript)

```
// Important: only works with non-negative weights
function dijkstra(graph, start) {
  const dist = {};
  const prev = {};
  const visited = new Set();
  for (const v in graph) {
    dist[v] = Infinity;
    prev[v] = null;
  }
  dist[start] = 0;

// Simplest priority queue (slow but compact)
  const pq = [{ v: start, d: 0 }];
  function push(node) { pq.push(node); }
  function popMin() {
    let best = 0;
    for (let i = 1; i < pq.length; i++) {
      if (pq[i].d < pq[best].d) best = i;
    }
    return pq.splice(best, 1)[0];
  }

while (pq.length) {
    const { v: u } = popMin();
    if (visited.has(u)) continue;
    visited.add(u);

for (const { to, w } of graph[u]) {
      const alt = dist[u] + w;
      if (alt < dist[to]) {
        dist[to] = alt;
        prev[to] = u;
        push({ v: to, d: alt });
      }
    }
  }

return { dist, prev };
}

function reconstructPath(prev, target) {
  const path = [];
  for (let v = target; v !== null; v = prev[v]) path.push(v);
  return path.reverse();
}

// Example usage
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 2 }],
  B: [{ to: 'C', w: 5 }, { to: 'D', w: 10 }],
  C: [{ to: 'E', w: 3 }],
  D: [{ to: 'F', w: 11 }],
  E: [{ to: 'D', w: 4 }],
  F: []
};

const { dist, prev } = dijkstra(graph, 'A');
console.log(dist); // shortest distances from A to the rest
console.log(reconstructPath(prev, 'D')); // example path A -> C -> E -> D
```

### Typical interview questions

- Which graph representation would you choose and why? (adjacency list vs matrix)
- Which shortest-path algorithm would you use with negative weights present? (Bellman-Ford; check for negative cycles)
- What do you do if weights are only 0 or 1? (0-1 BFS with a deque)
- How does an unweighted graph differ from a weighted one? (in an unweighted graph every weight equals 1, BFS is equivalent to Dijkstra)

### Brief summary

A weighted graph is an ordinary graph with an extra numeric label on its edges or vertices. This label sets the "cost" of a transition and makes it possible to solve practical problems such as finding the shortest path, choosing a minimum spanning tree, or an optimal route. The choice of data structure and algorithm depends on the properties of the weights (whether negative ones are present), the size, and the density of the graph.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts962 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.