Weighted Graphs

Definition and Terminology

Weighted Graph Concept

Weighted graph: graph G=(V,E) with function w: E → ℝ assigning scalar weights to edges. Weight: numerical value representing cost, distance, capacity, or other metrics. Purpose: model real-world relationships with quantitative attributes.

Vertices and Edges

Vertices (nodes): fundamental units or points in graph. Edges: connections between vertices, each with associated weight. Edge direction: directed or undirected. Weight sign: usually non-negative; negative values allowed in specific contexts.

Terminology Summary

Terminology includes: weighted edges, adjacency, degree, path, cycle, connectedness, edge weight function, and graph order and size.

Graph Representations

Adjacency Matrix

Adjacency matrix: |V|×|V| matrix A where A[i][j] = weight if edge (i,j) exists, else ∞ or 0 for no edge. Efficient for dense graphs. Space: O(V²). Access time: O(1) per edge lookup.

Adjacency List

Adjacency list: array/list of lists storing (neighbor, weight) pairs for each vertex. Efficient for sparse graphs. Space: O(V + E). Traversal time proportional to edges.

Edge List

Edge list: collection of edges with (source, destination, weight). Simple, compact. Useful for algorithms iterating over edges directly.

Types of Weighted Graphs

Directed Weighted Graphs

Edges have direction and weight. Used to model asymmetric relationships like traffic flow, web links, or precedence constraints.

Undirected Weighted Graphs

Edges have no direction but carry weight. Useful for symmetric relationships like road networks, communication links.

Positive and Negative Weights

Positive weights: common in distance, cost. Negative weights: allowed in contexts like profit/loss or certain algorithms but may cause cycles.

Special Cases

Zero weight edges: represent free connections or equivalence. Multi-weighted graphs: edges carry multiple attributes, e.g., cost and time.

Core Algorithms

Dijkstra’s Algorithm

Shortest path in graphs with non-negative edge weights. Mechanism: greedy selection of minimal tentative distance node. Time: O((V+E) log V) with priority queue.

Bellman-Ford Algorithm

Handles graphs with negative weights. Iterative relaxation over edges. Detects negative cycles. Time: O(VE).

Floyd-Warshall Algorithm

All-pairs shortest paths. Dynamic programming approach. Time: O(V³). Space: O(V²).

Kruskal’s and Prim’s Algorithms

Minimum spanning tree algorithms. Kruskal’s: edge sorting and union-find. Prim’s: growing MST from a start vertex using priority queue.

function Dijkstra(Graph, source): dist[source] ← 0 for each vertex v in Graph: if v ≠ source: dist[v] ← ∞ Q ← all vertices in Graph while Q not empty: u ← vertex in Q with min dist[u] remove u from Q for each neighbor v of u: alt ← dist[u] + weight(u, v) if alt < dist[v]: dist[v] ← alt return dist 

Shortest Path Problems

Single-Source Shortest Path

Compute shortest paths from one source vertex to all others. Algorithms: Dijkstra, Bellman-Ford.

All-Pairs Shortest Path

Find shortest paths between every pair of vertices. Algorithms: Floyd-Warshall, repeated Dijkstra.

Applications

Routing, navigation, network latency optimization, resource allocation.

Minimum Spanning Tree

Definition

Subgraph connecting all vertices with minimal total edge weight and no cycles. Exists only in connected undirected graphs.

Algorithms

Kruskal’s: sort edges, add if no cycle. Prim’s: grow MST from a vertex by adding the lowest-weight edge to new vertex.

Complexity

Kruskal’s: O(E log E). Prim’s: O(E + V log V) with priority queue.

Applications

Network Routing

Weighted graphs model communication networks. Weights represent latency, bandwidth cost, or reliability. Algorithms find optimal routing paths.

Transport and Logistics

Road networks, airline routes modeled as weighted graphs. Weights: distance, time, fuel cost. Used for route optimization, scheduling.

Resource Allocation

Weighted graph models task dependencies and costs. Applied in project planning, assembly lines, and workflow optimization.

Social Networks

Weights represent strength of relationships, interaction frequency, or influence.

Computational Complexity

Time Complexity Factors

Depends on graph representation, algorithm choice, graph density (sparse vs dense). Priority queues and heaps improve performance.

Space Complexity Considerations

Adjacency matrix requires O(V²) space; adjacency list O(V+E). Large graphs demand sparse representations and memory optimization.

Algorithmic Limitations

Negative weight cycles prevent shortest path solutions. NP-hard problems arise in weighted graphs, e.g., traveling salesman problem.

Storage and Memory Considerations

Data Structures

Arrays, linked lists, hash maps store adjacency lists. Specialized structures like Fibonacci heaps optimize priority queue operations.

Compression Techniques

Graph compression reduces memory: adjacency list compression, edge weight quantization.

Persistent and Dynamic Graphs

Support incremental updates and queries. Use balanced trees, segment trees, or dynamic connectivity data structures.

Visualization Techniques

Graph Layouts

Force-directed, circular, hierarchical layouts aid comprehension. Edge weight can be shown by line thickness, color intensity.

Interactive Tools

Zoom, filter, and highlight features enable exploration of weighted graphs. Software examples: Gephi, Cytoscape.

Challenges

Large graphs clutter visualization. Techniques: clustering, abstraction, edge bundling.

Advanced Topics

Multi-Weighted Graphs

Edges carry vectors of weights representing multiple criteria. Multi-objective optimization required.

Dynamic Weighted Graphs

Weights change over time. Algorithms adapt to maintain shortest paths or MST dynamically.

Probabilistic Weighted Graphs

Weights represent probabilities or uncertainties. Used in stochastic processes and network reliability.

Graph Neural Networks

Learn representations from weighted graphs for machine learning tasks. Weights influence message passing and node embedding.

Example Case Study

Problem Setup

Find shortest path from vertex A to all others in a directed weighted graph modeling city transport with distances as weights.

Graph Representation

Adjacency list used for sparse network. Edges stored as (neighbor, distance).

Algorithm Application

Dijkstra’s algorithm applied. Priority queue maintains vertices with tentative distances.

Graph = { 'A': [('B', 4), ('C', 2)], 'B': [('C', 5), ('D', 10)], 'C': [('E', 3)], 'D': [('F', 11)], 'E': [('D', 4)]}source = 'A'dist = Dijkstra(Graph, source)print(dist) 

Result Interpretation

Distances represent shortest travel distance from A. Used to optimize routing and scheduling.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 3rd ed., 2009, pp. 637-675.
• Jon Kleinberg, Éva Tardos, Algorithm Design, Pearson, 2005, pp. 388-420.
• Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, pp. 596-632.
• Andrea Goldsmith, Wireless Communications, Cambridge University Press, 2005, pp. 45-70.
• David A. Bader, High Performance Algorithms for Graph Analysis, Wiley, 2017, pp. 101-135.