What Is a Weighted Graph: Definition and Examples

A weighted graph is a type of graph where each connection (edge) between points (nodes) has a number called a weight. These weights represent values like cost, distance, or time, helping to measure how strong or important each connection is.

How It Works

A weighted graph is like a map where cities are points and roads between them have numbers showing distances or travel costs. Instead of just knowing which cities connect, you also know how far or expensive it is to travel between them.

Imagine you want to find the shortest path from your home to a friend's house. The weighted graph helps by showing not just the roads but also how long each road takes, so you can pick the quickest route. Each edge's weight guides decisions based on the value it represents.

Example

This example shows a weighted graph using a dictionary where keys are nodes and values are lists of connected nodes with their weights.

python

graph = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('C', 2), ('D', 6)],
    'C': [('A', 3), ('B', 2), ('D', 7)],
    'D': [('B', 6), ('C', 7)]
}

for node, edges in graph.items():
    print(f"Node {node} connects to:")
    for (neighbor, weight) in edges:
        print(f"  - {neighbor} with weight {weight}")

Output

Node A connects to:
  - B with weight 5
  - C with weight 3
Node B connects to:
  - A with weight 5
  - C with weight 2
  - D with weight 6
Node C connects to:
  - A with weight 3
  - B with weight 2
  - D with weight 7
Node D connects to:
  - B with weight 6
  - C with weight 7

When to Use

Weighted graphs are useful when you need to consider the cost or value of connections, not just their existence. For example, they help in:

• Finding the shortest or cheapest path in maps and GPS navigation.
• Modeling networks where edges have capacities or costs, like internet routing or transportation.
• Planning projects where tasks depend on others with different durations or costs.

Whenever you want to measure or optimize based on connection values, weighted graphs are the right choice.

Key Points

• A weighted graph assigns a number (weight) to each edge.
• Weights represent things like distance, cost, or time.
• They help find optimal paths or analyze networks with varying connection values.
• Weighted graphs can be directed or undirected depending on edge direction.

Key Takeaways

A weighted graph includes numbers on edges to show cost or distance.

Weights help find the best path or analyze connection strength.

Use weighted graphs when connection values matter, like in maps or networks.

They can be directed or undirected depending on the problem.

Represent weighted graphs with lists or dictionaries including weights.