Weighted Graphs

Overview

A weighted graph represents a collection of nodes (vertices) connected by edges, where each edge carries a numerical value representing cost, distance, capacity, or another metric. Unlike unweighted graphs that treat all connections equally, weighted graphs model real-world scenarios where relationships between entities have varying significance.

The concept emerged from operations research and network analysis in the 1950s, particularly through Edsger Dijkstra's shortest path algorithm (1956) and the study of transportation networks. Weighted graphs appear throughout software systems: network routing protocols use them to find optimal paths, recommendation systems model user preferences as weighted connections, and compilers represent program dependencies with weighted directed acyclic graphs.

Two fundamental variants exist: directed weighted graphs (digraphs) where edges have direction, and undirected weighted graphs where edges represent bidirectional connections. A social network might use undirected edges with weights representing interaction frequency, while a delivery route planner uses directed edges with weights representing one-way street distances.

# Simple weighted graph representation
graph = {
  'A' => { 'B' => 4, 'C' => 2 },
  'B' => { 'A' => 4, 'C' => 1, 'D' => 5 },
  'C' => { 'A' => 2, 'B' => 1, 'D' => 8 },
  'D' => { 'B' => 5, 'C' => 8 }
}
# A connects to B (weight 4) and C (weight 2)
# B connects to A, C, and D with respective weights

The primary operations on weighted graphs include finding shortest paths between nodes, identifying minimum spanning trees that connect all nodes with minimum total weight, and detecting negative weight cycles that create paradoxical situations in certain algorithms. Different algorithms handle specific weight constraints: Dijkstra's algorithm requires non-negative weights, while Bellman-Ford handles negative weights but has higher computational cost.

Key Principles

A weighted graph G consists of a set V of vertices and a set E of edges, where each edge e connects two vertices and carries a weight w(e). For directed graphs, an edge (u, v) with weight w represents a connection from vertex u to vertex v with cost w. For undirected graphs, edge {u, v} represents a bidirectional connection.

The weight function assigns numerical values to edges based on the problem domain. In network routing, weights represent latency or bandwidth. In geographic mapping, weights represent physical distances. In financial systems, weights might represent transaction costs or risk factors. Negative weights appear in problems like arbitrage detection in currency exchange, where cycles with negative total weight indicate profitable opportunities.

Path weight calculation sums the weights of edges along a path. For path p = (v₀, v₁, v₂, ..., vₖ), the total weight equals w(v₀, v₁) + w(v₁, v₂) + ... + w(vₖ₋₁, vₖ). The shortest path between two vertices represents the path with minimum total weight among all possible paths. Multiple shortest paths may exist with equal weight.

# Path weight calculation
def path_weight(graph, path)
  weight = 0
  (0...path.length - 1).each do |i|
    current = path[i]
    next_node = path[i + 1]
    return Float::INFINITY unless graph[current] && graph[current][next_node]
    weight += graph[current][next_node]
  end
  weight
end

path = ['A', 'B', 'C', 'D']
# Calculates: weight(A->B) + weight(B->C) + weight(C->D)

Graph connectivity determines which paths exist. A strongly connected directed graph has a path from every vertex to every other vertex. A weakly connected directed graph becomes connected when treating edges as undirected. Connected components group vertices that can reach each other, which matters when operations require reachability between nodes.

Negative weight cycles create algorithmic challenges. A cycle whose edge weights sum to a negative value means traversing the cycle repeatedly decreases total path weight without bound, making the concept of "shortest path" undefined for vertices reachable from the cycle. Detection and handling of negative cycles distinguishes different shortest path algorithms.

The triangle inequality w(u, w) ≤ w(u, v) + w(v, w) holds in many real-world graphs but not all. Geographic distances satisfy the triangle inequality (going direct never costs more than going through an intermediate point), but other domains violate it. This property affects algorithm correctness and optimization opportunities.

Implementation Approaches

Three primary representations exist for weighted graphs, each with distinct performance characteristics and memory requirements.

Adjacency matrix representation uses a two-dimensional array where matrix[i][j] stores the weight of the edge from vertex i to vertex j. Non-existent edges typically use infinity, null, or a sentinel value. This representation excels for dense graphs where most vertex pairs connect. Edge existence checking and weight retrieval operate in O(1) constant time. Space complexity remains O(V²) regardless of actual edge count, making it inefficient for sparse graphs.

# Adjacency matrix (conceptual)
     A   B   C   D
A  [ 0   4   2  inf]
B  [ 4   0   1   5 ]
C  [ 2   1   0   8 ]
D  [inf  5   8   0 ]

# inf represents no edge
# Diagonal typically 0 (vertex to itself)

Adjacency list representation stores each vertex with a list of its outgoing edges and their weights. For each vertex, the structure maintains pairs of (neighbor, weight). This approach optimizes space for sparse graphs, using O(V + E) space proportional to actual edges. Iterating over a vertex's neighbors takes O(degree(v)) time, making it efficient for graph traversal algorithms that examine each edge once.

# Adjacency list structure
adjacency_list = {
  'A' => [['B', 4], ['C', 2]],
  'B' => [['A', 4], ['C', 1], ['D', 5]],
  'C' => [['A', 2], ['B', 1], ['D', 8]],
  'D' => [['B', 5], ['C', 8]]
}
# Each vertex maps to array of [neighbor, weight] pairs

Edge list representation stores edges as a collection of (source, destination, weight) tuples. This simple format suits algorithms that process edges sequentially, such as Kruskal's minimum spanning tree algorithm that sorts edges by weight. Edge lists use O(E) space and facilitate parallel processing since edges store independently. However, finding all edges from a specific vertex requires scanning the entire list in O(E) time.

# Edge list structure
edge_list = [
  ['A', 'B', 4],
  ['A', 'C', 2],
  ['B', 'C', 1],
  ['B', 'D', 5],
  ['C', 'D', 8]
]
# Each entry: [source, destination, weight]

Hybrid approaches combine representations for specific algorithm requirements. Storing both adjacency lists and a reverse adjacency list (incoming edges) supports efficient bidirectional search. Maintaining an adjacency matrix for frequent weight lookups alongside edge lists for sorting optimizes certain problem types at the cost of increased memory.

Selection criteria depend on graph density (edge count relative to maximum possible edges), operation frequency (insertions, deletions, lookups), and memory constraints. Dense graphs benefit from adjacency matrices when edge queries dominate operations. Sparse graphs with traversal-heavy algorithms favor adjacency lists. Algorithms processing edges independently work well with edge lists.

Ruby Implementation

Ruby's flexible data structures enable clean weighted graph implementations. Hash-based adjacency lists provide the most practical approach for general-purpose weighted graphs.

class WeightedGraph
  def initialize(directed: false)
    @graph = Hash.new { |h, k| h[k] = {} }
    @directed = directed
  end
  
  def add_edge(from, to, weight)
    @graph[from][to] = weight
    @graph[to][from] = weight unless @directed
  end
  
  def weight(from, to)
    @graph[from][to]
  end
  
  def neighbors(vertex)
    @graph[vertex].keys
  end
  
  def edges_from(vertex)
    @graph[vertex]
  end
  
  def vertices
    @graph.keys
  end
  
  def edge_count
    if @directed
      @graph.values.sum { |edges| edges.size }
    else
      @graph.values.sum { |edges| edges.size } / 2
    end
  end
end

# Usage
g = WeightedGraph.new(directed: true)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'D', 5)

g.neighbors('A')  # => ['B', 'C']
g.weight('A', 'B')  # => 4

The hash-based structure uses nested hashes: outer hash maps vertices to inner hashes, which map neighboring vertices to edge weights. Using Hash.new { |h, k| h[k] = {} } automatically initializes missing vertices with empty hashes, preventing nil reference errors during edge addition.

Edge weight updates replace existing values by reassigning to the same hash key. Edge removal uses hash deletion operations:

class WeightedGraph
  def remove_edge(from, to)
    @graph[from].delete(to) if @graph[from]
    @graph[to].delete(from) if !@directed && @graph[to]
  end
  
  def remove_vertex(vertex)
    # Remove vertex and all its edges
    @graph.delete(vertex)
    
    # Remove edges pointing to this vertex
    @graph.each_value do |edges|
      edges.delete(vertex)
    end
  end
end

Matrix representation suits dense graphs or when O(1) weight lookup justifies O(V²) space:

class MatrixWeightedGraph
  def initialize(vertices)
    @vertices = vertices
    @size = vertices.size
    @vertex_index = vertices.each_with_index.to_h
    @matrix = Array.new(@size) { Array.new(@size, Float::INFINITY) }
    @size.times { |i| @matrix[i][i] = 0 }
  end
  
  def add_edge(from, to, weight)
    i = @vertex_index[from]
    j = @vertex_index[to]
    @matrix[i][j] = weight
  end
  
  def weight(from, to)
    i = @vertex_index[from]
    j = @vertex_index[to]
    @matrix[i][j]
  end
  
  def neighbors(vertex)
    i = @vertex_index[vertex]
    @vertices.select.with_index do |v, j|
      @matrix[i][j] != Float::INFINITY && i != j
    end
  end
end

The matrix approach maintains a vertex-to-index mapping for O(1) lookups. Infinity represents absent edges, distinguishing them from zero-weight edges. The diagonal initializes to zero since vertex distance to itself equals zero.

Edge list implementation supports algorithms that process edges independently:

class EdgeListGraph
  Edge = Struct.new(:from, :to, :weight) do
    def <=>(other)
      weight <=> other.weight
    end
  end
  
  def initialize
    @edges = []
    @vertices = Set.new
  end
  
  def add_edge(from, to, weight)
    @edges << Edge.new(from, to, weight)
    @vertices.add(from)
    @vertices.add(to)
  end
  
  def edges
    @edges
  end
  
  def sorted_edges
    @edges.sort
  end
  
  def vertices
    @vertices.to_a
  end
end

Using a Struct for edges provides comparison operators for sorting by weight. This representation excels for Kruskal's algorithm, which requires sorted edges.

File I/O handling enables loading graphs from external sources:

class WeightedGraph
  def self.from_file(filename, directed: false)
    graph = new(directed: directed)
    File.readlines(filename).each do |line|
      from, to, weight = line.strip.split
      graph.add_edge(from, to, weight.to_f)
    end
    graph
  end
  
  def to_file(filename)
    File.open(filename, 'w') do |f|
      @graph.each do |from, edges|
        edges.each do |to, weight|
          f.puts "#{from} #{to} #{weight}"
        end
      end
    end
  end
end

Graph validation ensures data integrity:

class WeightedGraph
  def validate!
    @graph.each do |from, edges|
      edges.each do |to, weight|
        raise "Negative weight: #{from}->#{to}" if weight < 0 && !allow_negative?
        raise "Invalid weight: #{weight}" unless weight.is_a?(Numeric)
        raise "Self-loop: #{from}" if from == to && !allow_self_loops?
      end
    end
  end
  
  private
  
  def allow_negative?
    @allow_negative ||= false
  end
  
  def allow_self_loops?
    @allow_self_loops ||= false
  end
end

Common Patterns

Dijkstra's algorithm finds shortest paths from a source vertex to all other vertices in graphs with non-negative edge weights. The algorithm maintains a priority queue of vertices ordered by tentative distance from source, iteratively selecting the closest unvisited vertex and updating distances to its neighbors.

require 'set'

def dijkstra(graph, source)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  previous = {}
  unvisited = Set.new(graph.vertices)
  
  while unvisited.any?
    # Find unvisited vertex with minimum distance
    current = unvisited.min_by { |v| distances[v] }
    break if distances[current] == Float::INFINITY
    
    unvisited.delete(current)
    
    # Update distances to neighbors
    graph.edges_from(current).each do |neighbor, weight|
      next unless unvisited.include?(neighbor)
      
      alt_distance = distances[current] + weight
      if alt_distance < distances[neighbor]
        distances[neighbor] = alt_distance
        previous[neighbor] = current
      end
    end
  end
  
  { distances: distances, previous: previous }
end

# Reconstruct shortest path
def shortest_path(previous, target)
  path = []
  current = target
  while current
    path.unshift(current)
    current = previous[current]
  end
  path
end

This implementation uses a simple linear search to find the minimum distance vertex. Production implementations use a priority queue (binary heap or Fibonacci heap) to reduce the find-minimum operation from O(V) to O(log V), improving overall complexity from O(V²) to O(E log V).

# Priority queue implementation using Ruby's SortedSet
require 'rbtree'

def dijkstra_optimized(graph, source)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  previous = {}
  
  # Priority queue: [distance, vertex]
  pq = RBTree.new
  pq[0] = source
  visited = Set.new
  
  until pq.empty?
    distance, current = pq.shift
    next if visited.include?(current)
    visited.add(current)
    
    graph.edges_from(current).each do |neighbor, weight|
      next if visited.include?(neighbor)
      
      alt_distance = distances[current] + weight
      if alt_distance < distances[neighbor]
        distances[neighbor] = alt_distance
        previous[neighbor] = current
        pq[alt_distance] = neighbor
      end
    end
  end
  
  { distances: distances, previous: previous }
end

Bellman-Ford algorithm handles graphs with negative edge weights and detects negative weight cycles. The algorithm relaxes all edges V-1 times, where V is the vertex count. If the V-th iteration still updates distances, a negative cycle exists.

def bellman_ford(graph, source)
  distances = Hash.new(Float::INFINITY)
  distances[source] = 0
  previous = {}
  vertices = graph.vertices
  
  # Relax edges V-1 times
  (vertices.size - 1).times do
    vertices.each do |u|
      graph.edges_from(u).each do |v, weight|
        alt_distance = distances[u] + weight
        if alt_distance < distances[v]
          distances[v] = alt_distance
          previous[v] = u
        end
      end
    end
  end
  
  # Check for negative cycles
  vertices.each do |u|
    graph.edges_from(u).each do |v, weight|
      if distances[u] + weight < distances[v]
        return { negative_cycle: true }
      end
    end
  end
  
  { distances: distances, previous: previous, negative_cycle: false }
end

The algorithm has O(VE) time complexity, making it slower than Dijkstra for dense graphs but necessary when negative weights exist. Applications include financial arbitrage detection and network flow problems.

Prim's algorithm computes minimum spanning trees for connected, undirected weighted graphs. The algorithm grows a tree from an arbitrary start vertex, repeatedly adding the minimum-weight edge connecting a tree vertex to a non-tree vertex.

def prim_mst(graph, start_vertex)
  mst_edges = []
  visited = Set.new([start_vertex])
  vertices = graph.vertices
  
  while visited.size < vertices.size
    min_edge = nil
    min_weight = Float::INFINITY
    
    # Find minimum edge crossing the cut
    visited.each do |u|
      graph.edges_from(u).each do |v, weight|
        next if visited.include?(v)
        
        if weight < min_weight
          min_weight = weight
          min_edge = [u, v, weight]
        end
      end
    end
    
    break unless min_edge
    
    from, to, weight = min_edge
    mst_edges << min_edge
    visited.add(to)
  end
  
  mst_edges
end

# Calculate total MST weight
def mst_weight(mst_edges)
  mst_edges.sum { |_, _, weight| weight }
end

Kruskal's algorithm provides an alternative MST approach using edge sorting and union-find data structure. The algorithm sorts edges by weight and adds each edge to the MST if it doesn't create a cycle.

class UnionFind
  def initialize(vertices)
    @parent = vertices.to_h { |v| [v, v] }
    @rank = vertices.to_h { |v| [v, 0] }
  end
  
  def find(vertex)
    if @parent[vertex] != vertex
      @parent[vertex] = find(@parent[vertex])  # Path compression
    end
    @parent[vertex]
  end
  
  def union(u, v)
    root_u = find(u)
    root_v = find(v)
    return false if root_u == root_v  # Already connected
    
    # Union by rank
    if @rank[root_u] < @rank[root_v]
      @parent[root_u] = root_v
    elsif @rank[root_u] > @rank[root_v]
      @parent[root_v] = root_u
    else
      @parent[root_v] = root_u
      @rank[root_u] += 1
    end
    true
  end
end

def kruskal_mst(graph)
  edges = []
  graph.vertices.each do |u|
    graph.edges_from(u).each do |v, weight|
      edges << [u, v, weight] if u < v  # Avoid duplicates in undirected graph
    end
  end
  
  edges.sort_by! { |_, _, weight| weight }
  uf = UnionFind.new(graph.vertices)
  mst_edges = []
  
  edges.each do |u, v, weight|
    if uf.union(u, v)
      mst_edges << [u, v, weight]
      break if mst_edges.size == graph.vertices.size - 1
    end
  end
  
  mst_edges
end

Floyd-Warshall algorithm computes shortest paths between all vertex pairs using dynamic programming. The algorithm considers paths through intermediate vertices, iteratively improving distance estimates.

def floyd_warshall(graph)
  vertices = graph.vertices
  n = vertices.size
  vertex_index = vertices.each_with_index.to_h
  
  # Initialize distance matrix
  dist = Array.new(n) { Array.new(n, Float::INFINITY) }
  next_vertex = Array.new(n) { Array.new(n) }
  
  n.times { |i| dist[i][i] = 0 }
  
  vertices.each do |u|
    graph.edges_from(u).each do |v, weight|
      i = vertex_index[u]
      j = vertex_index[v]
      dist[i][j] = weight
      next_vertex[i][j] = j
    end
  end
  
  # Floyd-Warshall iterations
  n.times do |k|
    n.times do |i|
      n.times do |j|
        if dist[i][k] + dist[k][j] < dist[i][j]
          dist[i][j] = dist[i][k] + dist[k][j]
          next_vertex[i][j] = next_vertex[i][k]
        end
      end
    end
  end
  
  { distances: dist, next_vertex: next_vertex, vertices: vertices }
end

def reconstruct_path_fw(result, from, to)
  vertex_index = result[:vertices].each_with_index.to_h
  i = vertex_index[from]
  j = vertex_index[to]
  return [] if result[:distances][i][j] == Float::INFINITY
  
  path = [from]
  while from != to
    i = vertex_index[from]
    j = vertex_index[to]
    from = result[:vertices][result[:next_vertex][i][j]]
    path << from
  end
  path
end

The O(V³) time complexity makes Floyd-Warshall suitable for small to medium graphs where all-pairs shortest paths are needed. The algorithm handles negative edges but not negative cycles.

Performance Considerations

Graph representation choice significantly impacts algorithm performance. Adjacency lists optimize sparse graph traversal, requiring O(V + E) space and O(degree(v)) time to iterate neighbors. Dense graphs with E approaching V² benefit from adjacency matrices that provide O(1) edge weight lookup at O(V²) space cost.

Dijkstra's algorithm complexity depends on priority queue implementation. Using a simple array for the priority queue yields O(V²) time complexity. Binary heap priority queues improve this to O((V + E) log V). Fibonacci heaps theoretically achieve O(E + V log V), though implementation complexity and constant factors often make binary heaps more practical.

# Comparing graph representations for neighbor iteration
require 'benchmark'

# Dense graph: 1000 vertices, ~500,000 edges
def benchmark_representations(vertex_count, edge_count)
  # Build adjacency list
  list_graph = {}
  vertex_count.times do |i|
    list_graph[i] = []
  end
  
  edge_count.times do
    from = rand(vertex_count)
    to = rand(vertex_count)
    weight = rand(1..100)
    list_graph[from] << [to, weight]
  end
  
  # Build adjacency matrix
  matrix_graph = Array.new(vertex_count) { Array.new(vertex_count, nil) }
  list_graph.each do |from, edges|
    edges.each do |to, weight|
      matrix_graph[from][to] = weight
    end
  end
  
  Benchmark.bm(20) do |x|
    x.report("List neighbor scan:") do
      10000.times do
        vertex = rand(vertex_count)
        list_graph[vertex].each { |to, weight| weight * 2 }
      end
    end
    
    x.report("Matrix neighbor scan:") do
      10000.times do
        vertex = rand(vertex_count)
        vertex_count.times do |i|
          weight = matrix_graph[vertex][i]
          weight * 2 if weight
        end
      end
    end
  end
end

Memory locality affects cache performance. Adjacency matrices store data contiguously, improving cache hit rates during dense graph operations. Adjacency lists scatter data across heap allocations, potentially causing cache misses. For algorithms that repeatedly access the same edges, matrix representation may perform better despite theoretical complexity disadvantages.

Negative weight handling separates algorithm classes. Dijkstra runs in O(E log V) with binary heap but fails with negative weights. Bellman-Ford handles negative weights in O(VE) time. Floyd-Warshall computes all-pairs shortest paths in O(V³), handling negative edges but detecting, not handling, negative cycles. Johnson's algorithm combines both approaches: use Bellman-Ford once to reweight edges, then run Dijkstra from each vertex, achieving O(V² log V + VE) for sparse graphs.

Minimum spanning tree algorithms exhibit different performance profiles. Prim's algorithm with binary heap runs in O(E log V), performing well on dense graphs. Kruskal's algorithm requires O(E log E) for edge sorting plus O(E α(V)) for union-find operations, where α is the inverse Ackermann function (effectively constant). Kruskal excels on sparse graphs where edge sorting dominates.

Parallel processing opportunities exist in weighted graph algorithms. Bellman-Ford's edge relaxation parallelizes naturally since each edge examines independently during each iteration. Floyd-Warshall's inner loops parallelize for each intermediate vertex k. Dijkstra's algorithm parallelizes less naturally due to priority queue synchronization, though Delta-stepping algorithm variants enable parallel shortest path computation.

# Parallel edge relaxation in Bellman-Ford (conceptual)
require 'concurrent'

def parallel_bellman_ford(graph, source, thread_count: 4)
  distances = Concurrent::Hash.new(Float::INFINITY)
  distances[source] = 0
  previous = Concurrent::Hash.new
  vertices = graph.vertices
  edges = []
  
  # Collect all edges
  vertices.each do |u|
    graph.edges_from(u).each do |v, weight|
      edges << [u, v, weight]
    end
  end
  
  # Parallel edge relaxation
  (vertices.size - 1).times do
    pool = Concurrent::FixedThreadPool.new(thread_count)
    
    edges.each do |u, v, weight|
      pool.post do
        alt = distances[u] + weight
        if alt < distances[v]
          distances[v] = alt
          previous[v] = u
        end
      end
    end
    
    pool.shutdown
    pool.wait_for_termination
  end
  
  { distances: distances.to_h, previous: previous.to_h }
end

Approximation algorithms trade accuracy for performance on large graphs. For shortest paths, A* algorithm uses heuristics to guide search, reducing explored vertices. For traveling salesman problems on weighted graphs, Christofides algorithm guarantees solutions within 1.5× optimal in O(V³) time. Metric TSP admits 1.5-approximation while general weighted graphs remain NP-hard even to approximate closely.

Practical Examples

Network Routing: Internet routing protocols model networks as weighted directed graphs where edge weights represent link costs based on bandwidth, latency, or administrative policies. The protocol computes shortest paths to determine packet forwarding tables.

class NetworkRouter
  def initialize
    @network = WeightedGraph.new(directed: true)
  end
  
  def add_link(from_router, to_router, cost)
    @network.add_edge(from_router, to_router, cost)
  end
  
  def compute_routing_table(source)
    result = dijkstra(@network, source)
    distances = result[:distances]
    previous = result[:previous]
    
    routing_table = {}
    @network.vertices.each do |dest|
      next if dest == source
      
      path = shortest_path(previous, dest)
      next if path.empty?
      
      # Next hop is second vertex in shortest path
      next_hop = path[1]
      routing_table[dest] = {
        next_hop: next_hop,
        distance: distances[dest],
        path: path
      }
    end
    
    routing_table
  end
  
  def handle_link_failure(from, to)
    @network.remove_edge(from, to)
    # Trigger routing table recomputation
  end
end

# Usage
router = NetworkRouter.new
router.add_link('R1', 'R2', 10)
router.add_link('R1', 'R3', 5)
router.add_link('R2', 'R4', 1)
router.add_link('R3', 'R4', 8)
router.add_link('R3', 'R2', 3)

table = router.compute_routing_table('R1')
# Routes packets from R1 to all reachable routers
# R1 -> R4: via R2 (cost 14)

GPS Navigation: Mapping applications represent road networks as weighted graphs where vertices represent intersections and edges represent road segments. Edge weights combine distance, speed limits, traffic conditions, and user preferences.

class GPSNavigator
  def initialize
    @road_network = WeightedGraph.new(directed: true)
    @coordinates = {}
  end
  
  def add_road(from_intersection, to_intersection, distance, speed_limit)
    travel_time = (distance / speed_limit.to_f) * 60  # minutes
    @road_network.add_edge(from_intersection, to_intersection, travel_time)
  end
  
  def set_coordinates(intersection, lat, lon)
    @coordinates[intersection] = { lat: lat, lon: lon }
  end
  
  def find_route(start, destination, prefer: :time)
    if prefer == :time
      result = dijkstra(@road_network, start)
    else
      # Recalculate weights for distance preference
      # Would require rebuilding graph or maintaining multiple weight sets
    end
    
    path = shortest_path(result[:previous], destination)
    total_time = result[:distances][destination]
    
    {
      path: path,
      estimated_time: total_time,
      instructions: generate_turn_by_turn(path)
    }
  end
  
  def update_traffic(from, to, delay_factor)
    current_weight = @road_network.weight(from, to)
    new_weight = current_weight * delay_factor
    @road_network.add_edge(from, to, new_weight)
  end
  
  private
  
  def generate_turn_by_turn(path)
    instructions = []
    path.each_cons(2) do |from, to|
      instructions << "Continue to #{to}"
    end
    instructions
  end
end

Project Dependency Management: Software build systems model project dependencies as weighted directed acyclic graphs. Vertices represent tasks or modules, edges represent dependencies, and weights represent build times or priority levels.

class BuildSystem
  Task = Struct.new(:name, :build_time, :dependencies)
  
  def initialize
    @tasks = {}
    @graph = WeightedGraph.new(directed: true)
  end
  
  def add_task(name, build_time:, dependencies: [])
    @tasks[name] = Task.new(name, build_time, dependencies)
    dependencies.each do |dep|
      @graph.add_edge(dep, name, @tasks[dep].build_time)
    end
  end
  
  def critical_path
    # Find longest path (critical path) using topological sort
    sorted = topological_sort
    distances = Hash.new(0)
    previous = {}
    
    sorted.each do |task|
      @graph.edges_from(task).each do |dependent, weight|
        alt = distances[task] + weight
        if alt > distances[dependent]
          distances[dependent] = alt
          previous[dependent] = task
        end
      end
    end
    
    # Find task with maximum distance
    end_task = distances.max_by { |_, dist| dist }[0]
    
    path = []
    current = end_task
    while current
      path.unshift(current)
      current = previous[current]
    end
    
    {
      path: path,
      total_time: distances[end_task],
      tasks: path.map { |t| @tasks[t] }
    }
  end
  
  private
  
  def topological_sort
    in_degree = Hash.new(0)
    @graph.vertices.each do |v|
      @graph.edges_from(v).each do |neighbor, _|
        in_degree[neighbor] += 1
      end
    end
    
    queue = @graph.vertices.select { |v| in_degree[v] == 0 }
    sorted = []
    
    while queue.any?
      current = queue.shift
      sorted << current
      
      @graph.edges_from(current).each do |neighbor, _|
        in_degree[neighbor] -= 1
        queue << neighbor if in_degree[neighbor] == 0
      end
    end
    
    sorted
  end
end

# Usage
build = BuildSystem.new
build.add_task('parse', build_time: 5)
build.add_task('compile', build_time: 20, dependencies: ['parse'])
build.add_task('test', build_time: 15, dependencies: ['compile'])
build.add_task('package', build_time: 10, dependencies: ['test'])

critical = build.critical_path
# Identifies longest build chain determining minimum build time

Social Network Analysis: Social platforms model user connections as weighted undirected graphs where edge weights represent interaction frequency, relationship strength, or shared interests. Algorithms identify communities, recommend connections, and detect influential users.

class SocialNetwork
  def initialize
    @network = WeightedGraph.new(directed: false)
    @user_data = {}
  end
  
  def add_friendship(user1, user2, interaction_score: 1)
    @network.add_edge(user1, user2, interaction_score)
  end
  
  def update_interaction(user1, user2, additional_score)
    current = @network.weight(user1, user2) || 0
    @network.add_edge(user1, user2, current + additional_score)
  end
  
  def friend_recommendations(user, count: 5)
    # Friends of friends weighted by mutual connection strength
    direct_friends = @network.neighbors(user).to_set
    recommendations = Hash.new(0)
    
    direct_friends.each do |friend|
      @network.neighbors(friend).each do |friend_of_friend|
        next if friend_of_friend == user
        next if direct_friends.include?(friend_of_friend)
        
        # Weight by strength of intermediate connection
        friend_strength = @network.weight(user, friend)
        recommendations[friend_of_friend] += friend_strength
      end
    end
    
    recommendations.sort_by { |_, score| -score }.first(count).to_h
  end
  
  def connection_strength(user1, user2)
    # Measure strength using shortest path weight
    result = dijkstra(@network, user1)
    distance = result[:distances][user2]
    
    return 0 if distance == Float::INFINITY
    
    # Convert distance to strength (inverse relationship)
    1.0 / distance
  end
end

Arbitrage Detection: Financial systems detect arbitrage opportunities in currency exchange by modeling exchange rates as weighted directed graphs. A negative weight cycle indicates a profitable trading sequence.

class CurrencyExchange
  def initialize
    @rates = WeightedGraph.new(directed: true)
  end
  
  def add_rate(from_currency, to_currency, exchange_rate)
    # Use negative log to convert multiplication to addition
    weight = -Math.log(exchange_rate)
    @rates.add_edge(from_currency, to_currency, weight)
  end
  
  def find_arbitrage
    # Use Bellman-Ford to detect negative cycles
    currencies = @rates.vertices
    return nil if currencies.empty?
    
    source = currencies.first
    distances = Hash.new(Float::INFINITY)
    distances[source] = 0
    previous = {}
    
    # Relax edges V-1 times
    (currencies.size - 1).times do
      currencies.each do |from|
        @rates.edges_from(from).each do |to, weight|
          alt = distances[from] + weight
          if alt < distances[to]
            distances[to] = alt
            previous[to] = from
          end
        end
      end
    end
    
    # Check for negative cycle
    currencies.each do |from|
      @rates.edges_from(from).each do |to, weight|
        if distances[from] + weight < distances[to]
          # Found negative cycle - reconstruct it
          cycle = reconstruct_cycle(previous, to)
          return {
            cycle: cycle,
            profit: calculate_profit(cycle)
          }
        end
      end
    end
    
    nil  # No arbitrage found
  end
  
  private
  
  def reconstruct_cycle(previous, start)
    cycle = [start]
    visited = Set.new([start])
    current = previous[start]
    
    while current && !visited.include?(current)
      cycle.unshift(current)
      visited.add(current)
      current = previous[current]
    end
    
    # Trim to actual cycle
    cycle_start_index = cycle.index(current)
    cycle[cycle_start_index..-1]
  end
  
  def calculate_profit(cycle)
    amount = 1.0
    cycle.each_cons(2) do |from, to|
      rate = Math.exp(-@rates.weight(from, to))
      amount *= rate
    end
    amount - 1.0  # Profit percentage
  end
end

# Usage
exchange = CurrencyExchange.new
exchange.add_rate('USD', 'EUR', 0.85)
exchange.add_rate('EUR', 'GBP', 0.90)
exchange.add_rate('GBP', 'USD', 1.35)

arbitrage = exchange.find_arbitrage
# Detects if USD -> EUR -> GBP -> USD yields profit

Reference

Graph Representations Comparison

Shortest Path Algorithms

Minimum Spanning Tree Algorithms

Common Graph Operations

Ruby Graph Implementation Patterns

Weight Types and Transformations

Algorithm Selection Guide

Common Edge Cases

Time Complexity Summary