Graph Optimization Algorithms

Introduction and Context

Graphs model relationships, routes, dependencies, and resource transfers. In an AI and ML system, a graph may represent a road network, a knowledge graph, a communication topology, a state space, or a bipartite relation between users and items. Graph optimization algorithms seek a structure or decision that minimizes cost, maximizes capacity, or satisfies constraints.

This chapter develops four central families of algorithms: shortest paths, minimum spanning trees, network flows, and matchings. The choice of algorithm depends on graph direction, edge weights, negative costs, connectivity, capacity constraints, and whether the objective concerns paths, global connectivity, or resource allocation.

Learning Objectives

By the end of this chapter, a student should be able to:

• formulate graph optimization problems precisely;
• select an appropriate shortest-path algorithm and justify its assumptions;
• compute and explain minimum spanning trees;
• formulate maximum-flow and related demand-satisfaction problems;
• distinguish matching, maximal matching, maximum matching, and perfect matching;
• assess correctness, complexity, scalability, and limitations;
• apply these methods to analytics and AI-related systems.

1. Foundations and Terminology

A weighted graph is written as G = (V, E), where V is the set of vertices and E is the set of edges. An edge may be directed, such as (u,v), or undirected, such as {u,v}. A weight w(u,v) can represent distance, time, monetary cost, risk, or negative utility. Unless stated otherwise, n = |V| and m = |E|.

A path is a sequence of vertices connected by edges. Its weight is the sum of its edge weights. A cycle begins and ends at the same vertex. A connected undirected graph has a path between every pair of vertices. A directed graph is strongly connected if every vertex can reach every other vertex.

Optimization problems require more than a feasible answer. A shortest path has minimum total weight; a minimum spanning tree has minimum total edge weight among all spanning trees; a maximum flow sends the greatest feasible quantity; and a maximum matching contains the greatest number of selected non-conflicting edges.

A useful distinction is between a graph's representation and its algorithm. Adjacency lists use O(n+m) space and are usually appropriate for sparse graphs. An adjacency matrix uses O(n²) space and supports constant-time edge lookup, making it useful for dense graphs and Floyd–Warshall.

2. Shortest-Path Algorithms

For a source vertex s, the single-source shortest-path problem seeks the minimum distance d(s,v) to every reachable vertex v. A shortest-path tree stores predecessor edges that reconstruct such paths. If a negative-weight cycle is reachable from s, distances to vertices reachable after repeated traversal of that cycle are not finite.

2.1 Relaxation

The central operation is relaxation. For an edge (u,v), if

d[v] > d[u] + w(u,v),

then set d[v] = d[u] + w(u,v) and predecessor[v] = u. Initialization sets d[s] = 0 and all other distances to infinity. Relaxation is valid because any path ending with (u,v) has length d[u] + w(u,v).

2.2 Breadth-First Search for Unweighted Graphs

When every edge has equal cost, usually unit cost, breadth-first search (BFS) finds shortest paths by number of edges. It explores vertices in nondecreasing distance layers. Its complexity with adjacency lists is O(n+m). BFS should not be treated as a weighted shortest-path algorithm unless weights are uniform.

2.3 Dijkstra's Algorithm

Dijkstra's algorithm repeatedly selects the unsettled vertex with the smallest tentative distance and permanently settles it. It relies on the condition that every edge weight is nonnegative. Once u is selected, any alternative route reaching u later cannot be cheaper, because extending a path cannot reduce its cost.

With a binary heap and adjacency lists, the complexity is O((n+m) log n), commonly written O(m log n) for connected graphs. With an array implementation it is O(n²), which can be competitive for dense graphs.

Worked example. Consider directed edges A→B = 4, A→C = 1, C→B = 2, B→D = 1, and C→D = 5. Initially d(A)=0. Relaxing from A gives d(B)=4 and d(C)=1. Selecting C next gives d(B)=3 and d(D)=6. Selecting B gives d(D)=4. Thus the shortest A-to-D path is A→C→B→D, with cost 1+2+1=4. The direct route through C→D costs 1+5=6.

2.4 Bellman–Ford Algorithm

Bellman–Ford handles directed graphs with negative edge weights and detects negative cycles reachable from the source. It relaxes every edge n−1 times. A simple path without repeated vertices has at most n−1 edges, so after n−1 complete passes all finite shortest distances are established if no relevant negative cycle exists. A further successful relaxation indicates a reachable negative cycle.

Its complexity is O(nm), and it is generally slower than Dijkstra's algorithm. It is appropriate when negative weights matter or when negative-cycle detection is required.

2.5 Floyd–Warshall All-Pairs Shortest Paths

Floyd–Warshall computes distances between every ordered pair. Let D^(k)[i,j] be the shortest distance from i to j using only vertices 1 through k as possible intermediate vertices. The recurrence is

D^(k)[i,j] = min(D^(k−1)[i,j], D^(k−1)[i,k] + D^(k−1)[k,j]).

The in-place implementation is:

D[i,j] ← min(D[i,j], D[i,k] + D[k,j]).

Initialize D[i,i]=0, D[i,j]=w(i,j) for an edge, and infinity otherwise. The running time is O(n³), with O(n²) space. It is especially useful for dense graphs or when all-pairs answers are needed.

After execution, D[i,i] < 0 means that a negative cycle is reachable from i and can return to i; equivalently, a negative closed walk exists from i. It does not mean merely that a negative cycle is reachable from i without a return path. If a negative cycle affects a pair (i,j), there must be a route from i to the cycle and from the cycle to j.

2.6 Choosing a Shortest-Path Method

Use BFS for unweighted graphs, Dijkstra for nonnegative weights, Bellman–Ford for possible negative weights or negative-cycle detection from one source, and Floyd–Warshall for all-pairs results on moderate-sized dense graphs. For very large sparse graphs, repeated single-source algorithms may be preferable, although the required query pattern and weight conditions must be examined.

3. Minimum Spanning Trees

For a connected, undirected, weighted graph, a spanning tree connects every vertex with exactly n−1 edges and contains no cycle. A minimum spanning tree (MST) is a spanning tree with minimum total weight. An MST is not generally a shortest-path tree: an MST minimizes total network connection cost, whereas a shortest-path tree minimizes distances from a selected source.

3.1 Cut and Cycle Principles

The cut property states that a lightest edge crossing any cut is safe for inclusion in some MST. If the lightest edge is unique, it belongs to every MST. The cycle property states that a strictly heaviest edge on a cycle belongs to no MST. These properties justify greedy algorithms.

3.2 Kruskal's Algorithm

Kruskal's algorithm sorts edges by nondecreasing weight and scans them. It adds an edge if it connects two currently different components. A disjoint-set union structure supports Find and Union operations efficiently. With sorting, the complexity is O(m log m), usually expressed as O(m log n) in simple connected-graph settings.

3.3 Prim's Algorithm

Prim's algorithm starts from any vertex and repeatedly adds the cheapest edge joining the current tree to an outside vertex. With adjacency lists and a binary heap, its complexity is O(m log n); with an adjacency matrix it is O(n²). Different starting vertices can produce different MST edge sets when equal weights exist, but all produced trees have the same minimum total weight.

Worked example. For vertices A, B, C, D and edges AB=1, AC=4, BC=2, BD=5, CD=3, and AD=6, Kruskal selects AB=1, BC=2, and CD=3. These three edges connect all four vertices without a cycle, giving total cost 6. The edge AC=4 is rejected because A and C are already connected; BD=5 and AD=6 are unnecessary.

If the graph is disconnected, a spanning tree does not exist for the entire graph. Kruskal's algorithm instead returns a minimum spanning forest, one tree per connected component.

4. Network Flow

A flow network is a directed graph with source s, sink t, and nonnegative capacity c(u,v). A flow f must satisfy capacity constraints 0 ≤ f(u,v) ≤ c(u,v) and conservation at every vertex other than s and t: inflow equals outflow. The value |f| is the net flow leaving s.

The residual capacity of a forward edge is c(u,v)−f(u,v). A reverse residual edge represents the ability to cancel previously sent flow. Residual graphs are essential because a later augmentation may need to revise an earlier routing decision.

4.1 Ford–Fulkerson and Edmonds–Karp

Ford–Fulkerson repeatedly finds an s–t augmenting path in the residual graph and sends the bottleneck residual capacity along it. With integer capacities and suitable path choices, it terminates; arbitrary real capacities can create problematic behavior under some path-selection rules. Edmonds–Karp chooses augmenting paths by BFS and has O(nm²) worst-case complexity.

4.2 Max-Flow Min-Cut Theorem

An s–t cut partitions vertices into S and T, with s in S and t in T. Its capacity is the sum of capacities of directed edges from S to T. The maximum-flow min-cut theorem states that the maximum feasible flow value equals the minimum s–t cut capacity. This gives both an optimality certificate and a diagnostic: a saturated bottleneck cut limits all possible throughput.

Worked example. Suppose s→a has capacity 4, s→b has capacity 3, a→t has capacity 2, b→t has capacity 3, and a→b has capacity 2. Send 2 through s-a-t and 3 through s-b-t. The flow value is 5. The cut S={s,a,b}, T={t} has capacity 2+3=5, so no flow can exceed 5; the flow is optimal.

4.3 Demands, Lower Bounds, and Circulation

Maximum throughput and demand satisfaction are different objectives. A logistics network may ask, “What is the greatest amount deliverable?”—a maximum-flow problem. A hospital system may instead require each hospital to receive at least a specified quantity. That is a feasibility or lower-bound flow problem, not automatically a maximum-flow problem.

Lower bounds l(u,v) and upper capacities c(u,v), with l≤f≤c, can be handled through circulation with demands. Start with residual capacity c−l and assign each vertex a balance induced by lower-bound flow. Add a super-source and super-sink to test whether all balances can be satisfied. A feasible circulation certifies that every lower and upper bound can be respected. Additional source–sink constructions can optimize throughput after feasibility has been established. Node demands, supplies, and conservation requirements must be modeled explicitly rather than inferred from a maximum-flow value.

5. Matching and Assignment

A matching is a set of edges with no shared endpoint. A vertex is saturated by a matching if it is incident to a selected edge; otherwise it is unsaturated. A maximal matching cannot be enlarged by adding one edge, but it need not have maximum cardinality. A maximum matching has the largest possible number of edges.

A perfect matching covers every vertex in the graph. In a bipartite graph G=(L∪R,E), a matching that covers every vertex of L is called an L-saturating matching; it is not necessarily perfect unless it also covers every vertex of R. If |L|≠|R|, a perfect matching in the whole bipartite graph is impossible because every matched edge covers one vertex from each side.

5.1 Bipartite Matching and Augmenting Paths

An augmenting path alternates between unmatched and matched edges and begins and ends at unsaturated vertices. Flipping the status of its edges increases matching size by one. Berge's theorem states that a matching is maximum if and only if it has no augmenting path.

The basic augmenting-path algorithm repeatedly searches for such a path. For bipartite graphs, the Hopcroft–Karp algorithm finds a maximum-cardinality matching in O(m√n), improving on many straightforward implementations.

5.2 Matching as Flow

For bipartite matching, create a source connected to each left vertex with capacity 1, direct each allowed left-to-right edge with capacity 1, and connect each right vertex to the sink with capacity 1. An integral maximum flow corresponds to a matching because integer capacities yield an integral optimum. This reduction is useful for extensions involving capacities and side constraints.

Weighted matching assigns a value or cost to each permitted pair. The assignment problem seeks a one-to-one assignment optimizing total value, often using the Hungarian algorithm in O(n³) for an n×n cost matrix. Missing pairs can be represented as forbidden edges or suitably penalized entries, but the modeling choice must preserve the business constraint.

6. Integrated Applied Case: Emergency Medical Logistics

This is an illustrative case. A regional health authority must distribute medical supplies from a central depot to hospitals through roads. The road network is directed because some roads are one-way. Travel times are nonnegative and vary by route.

Background and problem. The authority wants reliable routes, a low-cost infrastructure backbone, and a plan that meets hospital minimum deliveries. It also wants to assign available specialist teams to hospitals without assigning a team twice.

Analysis. Dijkstra's algorithm computes fastest routes from the depot because travel times are nonnegative. If every hospital needs repeated pairwise travel-time queries, Floyd–Warshall may be considered for a moderate-sized network. A minimum spanning tree could identify a low-total-length backbone for installing communication links, but it would not necessarily preserve fastest depot-to-hospital routes. Flow models road capacities and identifies maximum possible throughput. However, if hospital h must receive at least demand l_h, lower bounds or node-demand circulation must be included; simply maximizing depot-to-hospital flow may leave a hospital underserved. Finally, a bipartite matching assigns teams on one side to hospitals on the other. A perfect matching is required only if every team and every hospital must be assigned exactly once; if there are more hospitals than teams, the realistic target may be a team-saturating maximum matching plus explicit priorities.

Approach and outcome. The authority can combine: Dijkstra for route selection; Kruskal or Prim for communication infrastructure; a lower-bound flow feasibility test for minimum hospital requirements; and weighted matching for team assignment. Each component has a distinct objective and should not be substituted for another. The resulting dashboard can report route time, bottleneck cut capacity, unmet demand, infrastructure cost, and unassigned teams.

Learning points. Correct modeling precedes algorithm selection. Network connectivity, path optimality, throughput, demand feasibility, and one-to-one assignment are different problems. Operational decisions should also include uncertainty, emergency priorities, and the possibility that edge capacities or travel times change.

7. Correctness, Engineering Practice, and Limitations

Greedy algorithms require proof conditions. Dijkstra fails with negative edges; Prim and Kruskal require undirected MST assumptions unless a different directed-arborescence problem is intended. Flow algorithms require correctly oriented capacities and conservation rules. Matching algorithms require accurate eligibility edges and a clear definition of whether all vertices or only one side must be covered.

Practical implementations should use predecessor or parent arrays, detect unreachable vertices, guard against integer overflow when adding infinity to a finite value, and validate input for duplicate edges and illegal capacities. For floating-point weights, tolerance policies may be needed when comparing nearly equal values. Large dynamic graphs may require incremental or approximate methods rather than recomputing from scratch.

In AI applications, graph weights can encode learned scores and therefore inherit bias from data. A recommendation matching system may systematically exclude groups if eligibility or scoring data are biased. Medical and logistics systems require auditability, privacy protection, access controls, and human oversight. Optimizing a proxy such as travel time may conflict with equity, reliability, or clinical urgency. These are governance constraints, not merely algorithmic details.

Contemporary systems often combine classical algorithms with learned components. A neural model may predict travel time or edge risk, while Dijkstra or flow optimization enforces hard feasibility constraints. This separation is valuable: learned predictions can be uncertain, whereas capacity, safety, and assignment constraints must remain explicit. Sensitivity analysis should test how route, flow, or matching decisions change under perturbed weights and capacities.

Best-Practice Algorithm Selection

1. Define vertices, edges, direction, units, and objective.

2. Check whether weights can be negative and whether cycles matter.

3. Determine whether one source, all pairs, or a global structure is required.

4. Distinguish maximum throughput from minimum-demand feasibility.

5. Distinguish maximum matching from maximal and perfect matching.

6. Select a representation consistent with graph density.

7. Record assumptions and produce an optimality or feasibility certificate where possible.

8. Test boundary cases: disconnected graphs, zero capacities, equal weights, negative cycles, and insufficient supply.

Chapter Summary

Shortest-path algorithms optimize routes: BFS handles unweighted graphs, Dijkstra handles nonnegative weights, Bellman–Ford handles negative edges and detects reachable negative cycles, and Floyd–Warshall computes all-pairs distances. In Floyd–Warshall, a negative diagonal entry indicates a negative cycle that is reachable from the vertex and can return to it. Minimum spanning trees minimize total connection cost, not source-to-vertex distances, and are obtained by cut-safe greedy methods such as Kruskal and Prim. Network flow models capacity and conservation; maximum throughput must be distinguished from satisfying specified lower demands, which may require circulation modeling. Matchings prevent shared endpoints; maximum, maximal, and perfect matching are distinct concepts. A perfect matching covers every vertex, whereas a matching saturating one bipartition need not cover the other. Correct algorithm selection depends on assumptions, objective, graph structure, and operational constraints.

Key Terms

Graph: A set of vertices and edges representing relationships.

Path: A sequence of connected vertices.

Relaxation: An operation that improves a tentative shortest-path distance.

Negative cycle: A cycle whose total edge weight is negative.

Shortest-path tree: A predecessor structure representing source shortest paths.

Minimum spanning tree: A minimum-weight tree spanning all vertices of a connected undirected graph.

Cut: A partition of vertices into two sets.

Disjoint-set union: A structure supporting component merging and representative queries.

Capacity: The maximum permitted flow on an edge.

Residual graph: A graph representing remaining and reversible flow capacity.

Augmenting path: A residual source-to-sink path used to increase flow.

Circulation: A flow satisfying balance constraints, generally without a distinguished net source-to-sink objective.

Matching: A set of edges sharing no endpoints.

Maximal matching: A matching that cannot be enlarged by adding one edge.

Maximum matching: A matching of greatest cardinality.

Perfect matching: A matching covering every vertex in the graph.

Bipartite graph: A graph whose vertices divide into two sets with edges only across the sets.

Optimality certificate: Evidence, such as a minimum cut, proving an obtained solution is optimal.

Review Questions

Short Answer Questions

1. Why does Dijkstra's algorithm require nonnegative edge weights?

2. State the difference between a shortest-path tree and a minimum spanning tree.

3. What does a negative diagonal entry in Floyd–Warshall's final matrix indicate?

4. Define residual capacity and explain the role of reverse residual edges.

5. Distinguish a maximum matching from a perfect matching.

Long Answer Questions

1. Explain relaxation and compare BFS, Dijkstra, Bellman–Ford, and Floyd–Warshall, including their assumptions and complexities.

2. Prove informally why Kruskal's algorithm is correct using the cut property.

3. State and explain the max-flow min-cut theorem and its practical significance.

4. Describe how bipartite matching can be reduced to maximum flow.

5. Explain why a logistics problem with hospital minimum deliveries may require lower-bound circulation rather than ordinary maximum flow.

Analytical / Application Questions

1. Design an algorithm for a road network with nonnegative travel times, frequent single-source queries, and occasional edge updates. Justify your representation and complexity.

2. A bipartite system has five teams and eight hospitals, with each team eligible for several hospitals. Specify whether a perfect matching is possible and formulate an appropriate objective if every team should be assigned but some hospitals may remain unassigned.

3. Construct a flow model for a supply network in which each of three hospitals has a minimum demand, roads have capacities, and the depot has limited supply. Identify what feasibility result would demonstrate that all minimum demands can be met.

Multiple Choice Questions with Answers

Question 1

Which algorithm is appropriate for single-source shortest paths when all edge weights are nonnegative?

A. Dijkstra's algorithm

B. Kruskal's algorithm

C. Floyd–Warshall only

D. Hopcroft–Karp algorithm

Correct Answer: A. Dijkstra's algorithm

Question 2

What does D[i,i] < 0 after Floyd–Warshall indicate?

A. A vertex is unreachable from i

B. A negative cycle can be reached from i and can return to i

C. Every edge leaving i is negative

D. The graph is disconnected

Correct Answer: B. A negative cycle can be reached from i and can return to i

Question 3

What is the total weight of an MST for edges selected with weights 1, 2, and 3?

A. 3

B. 5

C. 6

D. 9

Correct Answer: C. 6

Question 4

Which structure is commonly used by Kruskal's algorithm to detect whether an edge joins different components?

A. Queue

B. Disjoint-set union

C. Stack

D. Hash table of shortest paths

Correct Answer: B. Disjoint-set union

Question 5

According to the max-flow min-cut theorem, maximum flow value equals the capacity of the:

A. Largest cycle

B. Minimum s–t cut

C. Maximum spanning tree

D. Shortest path

Correct Answer: B. Minimum s–t cut

Question 6

Why may specified hospital minimum deliveries require circulation or lower-bound modeling?

A. Maximum flow always ignores capacities

B. Minimum requirements are constraints that ordinary throughput maximization does not guarantee

C. Dijkstra cannot process hospitals

D. Matching algorithms cannot use directed graphs

Correct Answer: B. Minimum requirements are constraints that ordinary throughput maximization does not guarantee

Question 7

Which statement correctly defines a perfect matching?

A. A matching that cannot be enlarged by one edge

B. A matching with the greatest number of edges among those considered

C. A matching that covers every vertex in the graph

D. A matching that covers only the left bipartition

Correct Answer: C. A matching that covers every vertex in the graph

Question 8

A matching that covers every vertex in the left side of a bipartite graph but not necessarily the right side is called:

A. An L-saturating matching

B. A perfect matching in all cases

C. A spanning tree

D. A negative matching

Correct Answer: A. An L-saturating matching

Question 9

What is the key optimality condition for a bipartite matching?

A. It contains no augmenting path

B. It contains every graph edge

C. It has exactly one edge

D. It has no isolated graph vertex outside the matching

Correct Answer: A. It contains no augmenting path

Question 10

For the illustrative flow network, if the only edges entering t have capacities 2 and 3, what is the maximum possible flow?

A. 2

B. 3

C. 4

D. 5

Correct Answer: D. 5