Weighted vs Unweighted Graphs

Weighted vs Unweighted Graphs

Graphs are used to model relationships between objects, but not every connection has the same meaning. Sometimes an edge simply represents that two vertices are connected. In other cases, an edge also carries a numerical value such as distance, cost, time, or capacity.

This distinction gives us two important graph types: unweighted graphs and weighted graphs.

What Is an Unweighted Graph?

An unweighted graph is a graph where edges represent connections without an associated numerical weight.

A --- B --- C
      |
      D

The edges show that the vertices are connected, but they do not specify how far apart the vertices are or how expensive it is to move between them.

For many problems, the important question is simply whether a connection exists or how many edges are required to reach one vertex from another.

What Is a Weighted Graph?

A weighted graph assigns a numerical value to each edge. This value is called the edge weight.

A --- 10 --- B
B --- 5 ---- C
A --- 20 --- C

Here, the connection between A and B has weight 10, the connection between B and C has weight 5, and the connection between A and C has weight 20.

The meaning of a weight depends on the problem. It may represent kilometers in a road network, milliseconds in a communication network, dollars in a financial network, or another numerical measurement.

The Main Difference

Understanding Edge Weights

A weight is simply a value associated with an edge. The value does not automatically mean distance. The application defines what the value represents.

A --- 15 --- B

The value 15 could mean 15 kilometers, 15 minutes, a cost of 15 units, or another measurement depending on the graph's purpose.

Path Cost in an Unweighted Graph

In an unweighted graph, a path is commonly measured by the number of edges it contains.

A --- B --- C --- D

The path A → B → C → D contains three edges, so its path length is 3.

This is why Breadth-First Search (BFS) can find a shortest path in an unweighted graph: BFS explores vertices level by level and therefore finds a path using the fewest edges.

Path Cost in a Weighted Graph

In a weighted graph, the cost of a path is commonly calculated by adding the weights of its edges.

A -- 4 -- B -- 3 -- C
A -------- 10 -------- C

There are two paths from A to C:

• A → B → C has cost 4 + 3 = 7.
• A → C has cost 10.

Although both paths connect the same vertices, the first path has the lower total weight.

Why BFS Is Not Enough for Weighted Shortest Paths

BFS minimizes the number of edges, not the sum of arbitrary edge weights.

A -- 1 -- B -- 1 -- C
A -------- 1 -------- D -- 1 -- C

More generally, a route with fewer edges can have a larger total weight than a route with more edges. Therefore, when edge weights affect the meaning of "shortest," a weighted shortest-path algorithm should be selected based on the properties of those weights.

Common Algorithms

The graph's weighting and edge properties influence which algorithm is appropriate.

Weighted and Unweighted Graph Representation

Both graph types can be represented using adjacency lists or adjacency matrices. The difference is that weighted representations need to store the edge's weight.

Unweighted Adjacency List

const graph = {
  A: ['B', 'C'],
  B: ['A', 'C'],
  C: ['A', 'B']
};

Weighted Adjacency List

const graph = {
  A: [
    { node: 'B', weight: 4 },
    { node: 'C', weight: 10 }
  ],
  B: [
    { node: 'A', weight: 4 },
    { node: 'C', weight: 3 }
  ],
  C: [
    { node: 'A', weight: 10 },
    { node: 'B', weight: 3 }
  ]
};

The weighted representation stores both the destination vertex and the corresponding edge weight.

Weighted Adjacency Matrix

In a weighted adjacency matrix, the matrix entry can store the edge weight instead of simply storing 0 or 1.

    A  B  C
A   0  4  10
B   4  0  3
C   10 3  0

The value at row A and column B represents the weight of the edge between A and B. The exact value used for "no edge" depends on the implementation and algorithm.

Positive and Negative Weights

Weighted graphs can contain different kinds of numerical values. In algorithm problems, it is important to determine whether negative edge weights are allowed.

• Non-negative weights: Values are zero or greater.
• Negative weights: Some edges have values below zero.
• Negative cycle: A cycle whose total weight is negative.

Dijkstra's algorithm relies on non-negative edge weights. When negative weights are possible, algorithms such as Bellman-Ford may be more appropriate depending on the task.

Directed and Weighted Are Separate Properties

It is important not to confuse direction with weight. A graph can have either property independently.

• Undirected and unweighted
• Undirected and weighted
• Directed and unweighted
• Directed and weighted

Undirected weighted:

A --- 10 --- B


Directed weighted:

A --- 10 ---> B

A directed weighted graph has both a direction and a numerical weight on its edges. The reverse edge, if present, is a separate directed edge.

Real-World Examples

Road Networks

Locations can be represented as vertices and roads as edges. If the distance between locations matters, the roads can be assigned weights representing distance.

Flight Networks

Airports can be vertices and flights can be edges. A weight might represent flight duration, ticket cost, or another measurable quantity.

Computer Networks

Devices can be represented as vertices and network links as edges. Weights can represent latency, bandwidth-related cost, or another network metric.

Social Networks

If the only requirement is whether two users are connected, an unweighted graph may be sufficient. If a relationship has a numerical strength or score, a weighted graph can represent that additional information.

Task Dependencies

A dependency graph can be directed and unweighted when only the dependency relationship matters. Additional numerical information can turn it into a weighted graph.

JavaScript Example: Weighted Graph

The following example creates a weighted undirected graph using an adjacency list.

const graph = {};

function addEdge(graph, a, b, weight) {
  if (!graph[a]) {
    graph[a] = [];
  }

  if (!graph[b]) {
    graph[b] = [];
  }

  graph[a].push({ node: b, weight });
  graph[b].push({ node: a, weight });
}

addEdge(graph, 'A', 'B', 4);
addEdge(graph, 'B', 'C', 3);
addEdge(graph, 'A', 'C', 10);

console.log(graph);

Finding the Lowest Direct Edge

A weighted graph can be inspected to compare the costs of direct connections. However, the lowest-weight direct edge is not necessarily part of the lowest-cost path between two vertices.

const graph = {
  A: [
    { node: 'B', weight: 4 },
    { node: 'C', weight: 10 }
  ]
};

const cheapest = graph.A.reduce((best, edge) =>
  edge.weight < best.weight ? edge : best
);

console.log(cheapest);
// { node: 'B', weight: 4 }

For complete shortest-path problems, the algorithm must consider the total cost of possible routes rather than examining only individual edges.

How to Choose Between Weighted and Unweighted

The choice depends on whether the relationship itself is enough to solve the problem or whether the connection has a meaningful numerical cost.

Common Mistakes

• Assuming every weighted graph represents physical distance.
• Using BFS to solve a weighted shortest-path problem when edge weights affect the result.
• Assuming the path with the fewest edges always has the lowest total weight.
• Ignoring whether negative edge weights are allowed.
• Confusing graph direction with edge weight.
• Forgetting to store weights when building a weighted adjacency list.
• Assuming the smallest individual edge automatically belongs to the optimal complete path.

Key Takeaways

• An unweighted graph represents connections without explicit numerical edge weights.
• A weighted graph associates numerical values with edges.
• In an unweighted graph, shortest paths are commonly measured by the number of edges.
• In a weighted graph, shortest paths commonly minimize the total edge weight.
• BFS is suitable for shortest paths by edge count in unweighted graphs.
• Dijkstra's algorithm is commonly used for shortest paths with non-negative weights.
• Bellman-Ford can handle negative edge weights under appropriate conditions.
• Direction and weight are independent graph properties.
• The meaning of an edge weight is determined by the application or problem.