Weighted graphs in Data Structures Theory - Full Explanation

Introduction

Imagine you want to find the shortest path between two cities, but the roads between them have different lengths or costs. Weighted graphs help solve this problem by showing connections with values that represent distance, cost, or time.

Explanation

Graph Basics

A graph is a collection of points called nodes or vertices connected by lines called edges. These edges show relationships or paths between the nodes. In a weighted graph, each edge has a number called a weight that gives extra information about the connection.

Graphs consist of nodes connected by edges, and weights add meaningful values to these edges.

Weights on Edges

Weights are numbers assigned to edges to represent things like distance, cost, or time needed to travel between nodes. These weights help in making decisions, such as choosing the shortest or cheapest path in the graph.

Weights quantify the cost or value of moving along an edge between two nodes.

Directed vs Undirected Weighted Graphs

In directed weighted graphs, edges have a direction, meaning the connection goes one way and the weight applies in that direction only. In undirected weighted graphs, edges have no direction, so the weight applies equally both ways between nodes.

Direction of edges affects how weights are interpreted in the graph.

Applications of Weighted Graphs

Weighted graphs are used in many real-world problems like GPS navigation, network routing, and project scheduling. They help find the best routes, minimize costs, or optimize resources by considering the weights on edges.

Weighted graphs model real problems where connections have different costs or values.

Real World Analogy

Imagine a city map where streets connect different places. Each street has a sign showing how long it takes to drive through. To get from your home to a friend's house quickly, you look for the route with the smallest total time, not just the fewest streets.

Graph Basics → City locations as points and streets as lines connecting them

Weights on Edges → Time or distance signs on each street showing how long it takes to travel

Directed vs Undirected Weighted Graphs → One-way streets (directed) versus two-way streets (undirected) with travel times

Applications of Weighted Graphs → Using the map to find the fastest or shortest route between places

Diagram

Diagram

┌─────────────┐       5       ┌─────────────┐
│     A       │──────────────▶│     B       │
└─────────────┘               └─────────────┘
      │ 3                         │ 2
      │                           │
      ▼                           ▼
┌─────────────┐       4       ┌─────────────┐
│     C       │◀──────────────│     D       │
└─────────────┘               └─────────────┘

A weighted directed graph with nodes A, B, C, D and edges labeled with weights showing travel costs.

Key Facts

Weighted graph → A graph where each edge has a numerical value called a weight.

Edge weight → A number assigned to an edge representing cost, distance, or time.

Directed weighted graph → A graph with edges that have direction and weights applying in that direction.

Undirected weighted graph → A graph with edges that have no direction and weights applying both ways.

Shortest path → The path between two nodes with the smallest total sum of edge weights.

Code Example

Data Structures Theory

graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'D': 2},
    'C': {'D': 4},
    'D': {}
}

# Print edges with weights
for node, edges in graph.items():
    for neighbor, weight in edges.items():
        print(f"Edge from {node} to {neighbor} has weight {weight}")

Common Confusions

Thinking weights only represent distance

Thinking weights only represent distance Weights can represent any measurable cost like time, money, or risk, not just distance.

Assuming all graphs with weights are directed

Assuming all graphs with weights are directed Graphs can be weighted and either directed or undirected; direction depends on the problem.

Believing the shortest path is always the one with fewest edges

Believing the shortest path is always the one with fewest edges The shortest path depends on the sum of weights, not the number of edges.

Summary

Weighted graphs add numbers to edges to represent costs like distance or time.

Edges can be directed or undirected, affecting how weights apply between nodes.

Weighted graphs help solve real problems like finding shortest or cheapest paths.