Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 49 ยท Network Optimization

Chapter 4 Overview: Network Optimization

Chapter 4 overview: nodes, arcs and weights, the main families of network problems, how to store a network in code and why network models are special.

Roads, pipelines, computer networks, supply chains, flights and even friendships can be drawn as dots joined by lines. Operations research has a rich toolbox for such networks, and the problems are so common that they have their own algorithms: shortest paths, minimum spanning trees, maximum flows, transportation and assignment. These algorithms are typically much faster than general linear programming, and their solutions are automatically whole numbers. This chapter teaches the main ones, with code you can run.

A network of six labelled nodes with weighted edges and the shortest route highlighted, beside a list of five network problem families
One network, many questions: the shortest route is highlighted in pink, and the five problem families of the chapter are listed at the right.

What you will learn

  • The vocabulary of networks: nodes, arcs, edges, weights, paths and cycles.
  • The five problem families of this chapter and when each applies.
  • How to store a network as a matrix or a list in Python.
  • Why network problems are easier than general integer programs.

Key terms

Node (vertex): a point of the network, such as a city or a warehouse.

Edge or arc: a connection between two nodes. An edge is undirected; an arc is directed (one-way).

Weight: a number on an edge, such as a distance, a cost or a capacity.

Path: a sequence of edges leading from one node to another without revisiting a node.

Cycle: a path that returns to its start. A tree is a connected network with no cycles.

From a map to a network

A road map has hills, houses and rivers. A routing problem needs none of that. It needs the junctions (nodes), the roads between them (edges) and how long each road is (weights). Throwing away everything else is modelling, in the sense of Chapter 2. After you do it, the same mathematics serves a delivery van, an internet packet and a data-center cable plan.

Networks can be:

  • Undirected, when travel works both ways, such as a two-way road.
  • Directed, when direction matters, such as one-way streets or a pipeline.
  • Weighted, when edges carry numbers such as lengths, times, costs or capacities.

Throughout the chapter we will use a small delivery network: a depot S, four towns A, B, C, D and a customer T, with road lengths in kilometers (example numbers).

The five families

Shortest path

Question Cheapest route A to B?
Method Dijkstra's algorithm

GPS navigation is a shortest-path engine.

1 / 5

Storing a network

There are two common representations.

An adjacency matrix is a table in which entry [i][j] is the weight of the edge from node i to node j, or 0 if there is no edge. It is easy to read and is what scipy.sparse.csgraph expects. An adjacency list stores, for each node, the list of its neighbours with weights. It uses less space for networks with few edges.

Python Build the delivery network and explore it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The next widget lets you ask the first network question yourself. Pick two towns and see the shortest route, found by Dijkstra's algorithm (explained in the shortest-path lesson).

Find the shortest route between two towns

Why networks are special

Every network problem can be written as a linear program (and the shortest path, flow, transportation and assignment problems all are, as you will see). What makes them special is their structure: each variable (the flow on an arc) appears in exactly two constraints, one at each end of the arc, with coefficients +1 and โˆ’1. Such matrices are totally unimodular, and the mathematical consequence is that the LP always has an integer optimal solution when the data are integers. So you can run simplex, or a specialized fast algorithm, and never need branch and bound. Specialized network algorithms exploit the structure further and handle millions of nodes.

What each lesson covers

  1. Shortest paths: Dijkstra's algorithm from scratch and with scipy.
  2. Minimum spanning trees: Kruskal's and Prim's algorithms.
  3. Maximum flow and minimum cut: augmenting paths and the max-flow min-cut theorem.
  4. Transportation and assignment: the two classic cost-minimizing network models.
  5. Chapter 4 review.

Common misconceptions

"A network must look like a map." The positions of nodes in a drawing carry no meaning; only the connections and weights do.

"Shortest means fewest edges." In a weighted network the shortest path has the smallest total weight, which can use more edges.

"Network problems need integer programming." For the classical ones, the LP solution is already integer.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the difference between an edge and an arc?

    An arc has a direction (one-way); an edge can be traveled both ways.
  2. 2. What is a tree in network terms?

    A tree is connected and acyclic; a spanning tree touches every node.
  3. 3. Which representation does scipy.sparse.csgraph expect?

    Entry [i][j] holds the weight of the edge from node i to node j.
  4. 4. Why do shortest path, transportation and assignment LPs have integer solutions?

    Total unimodularity of the network matrix makes every corner integer when the right sides are integers.

Summary

  • A network is nodes joined by weighted edges or arcs; drawings carry no extra meaning.
  • Five families: shortest path, minimum spanning tree, maximum flow, transportation and assignment.
  • Store networks as adjacency matrices or lists.
  • Network LPs have integer optimal solutions, and specialized algorithms are fast.

Next: Shortest Paths and Dijkstra's Algorithm