Introduction to Networks

Introduction to Networks – Eulerian Tours – The Shortest Path Problem – Applications of the shortest path problem – Dijkstra’s Algorithm for Solving the Shortest Path Problem 1 Network Models 2 z Optimization models that exhibit a very special structure. z For special cases, this structure to dramatically reduce computational complexity (running time). z First widespread application of LP to problems of industrial logistics z Addresses huge number of diverse applications z Today’s lecture (first of 3): introductory material, Eulerian tours, the Shortest Path Problem Notation and Terminology Note: Network terminology is not (and never will be) standardized. The same concept may be denoted in many different ways. Called: • NETWORK • directed graph • digraph • graph Class Handouts (Ahuja, Magnanti, Orlin) 1 3 2 4 Also Seen Graph G = (V,E) Network G = (N, A) Vertex set V = {1,2,3,4} Node set N = {1, 2, 3, 4} Edge set: Arc Set{(1,2), (1,3), (3,2), (3,4), (2,4)} E={1-2,1-3,3-2,3-4,2-4} 3 Directed and Undirected Networks 1 a 4 b c 2 1 e 3 d An Undirected Graph • a b c 2 e 4 3 d A Directed Graph Networks are used to transport commodities • physical goods (products, liquids) • communication • electricity, etc. • 4 The field of Network Optimization concerns optimization problems on networks Networks are Everywhere z z z 5 Physical Networks – Road Networks – Railway Networks – Airline traffic Networks – Electrical networks, e.g., the power grid Abstract networks – organizational charts – precedence relationships in projects Others? Overview: z z z z 6 Networks and graphs are powerful modeling tools. Most OR models have networks or graphs as a major aspect Next three lectures: we will develop models that are efficiently solvable. – Help form a toolkit for those problems that are harder to solve Next: representations of networks – A great insight from computer scientists: how data is represented is important to how it is used The Adjacency Matrix (for directed graphs) 1 2 1 a 4 b c 2 e 3 d A Directed Graph 1 2 3 4 ⎡0 ⎢0 ⎢ ⎢0 ⎢ ⎣0 1 0 0 1 3 0 1 0 1 4 1⎤ 0⎥ ⎥ 0⎥ ⎥ 0⎦ •Have a row for each node •Have a column for each node •Put a 1 in row i- column j if (i, j) is an arc What would happen if (4, 2) became (2, 4)? 7 The Adjacency Matrix (for undirected graphs) 1 2 1 b c a 4 2 e 3 d An Undirected Graph 1 2 3 4 ⎡0 ⎢1 ⎢ ⎢0 ⎢ ⎣1 1 0 1 1 3 0 1 0 1 4 degree 1⎤ 1⎥ ⎥ 1⎥ ⎥ 0⎦ 2 3 2 3 •Have a row for each node •Have a column for each node •Put a 1 in row i- column j if (i, j) is an arc The degree of a node is the number of incident arcs 8 Representation of arc lists (for directed graphs) 1 a 4 b 1: (1,2), (1,4) 2 c e 3 d A Directed Graph 2: (2,3) 3: ∅ 4: (4,2), (4,3) •Create a list arcs for each node •There are lots of very similar variants of this type of representation 9 On network representations 10 z Each representation has its advantages – Major purpose of a representation • efficiency in algorithms • ease of use z Next: definitions for networks Path: Example: 5, 2, 3, 4. (or 5, c, 2, b, 3, e, 4) •No node is repeated. •Directions are ignored. 1 Directed Path . Example: 1, 2, 5, 3, 4 (or 1, a, 2, c, 5, d, 3, e, 4) •No node is repeated. •Directions are important. Cycle (or circuit or loop) 1, 2, 3, 1. (or 1, a, 2, b, 3, e) •A path with 2 or more nodes, except that the first node is the last node. •Directions are ignored. Directed Cycle: (1, 2, 3, 4, 1) or 1, a, 2, b, 3, c, 4, d, 1 •No node is repeated, except that the first 5 c a b 2 c 1 a a 2 5 d 3 e d b 3 e 11 4 2 b e 1 d 3 c 4 a 2 b e 1 d c node is the last node. •Directions are important. 4 4 3 Walks 1 a 4 b 2 c 1 e 3 d 5 a 4 b 2 c e 3 d 5 Walks are paths that can repeat nodes and arcs Example of a directed walk: 1-2-3-5-4-2-3-5 A walk is closed if its first and last nodes are the same. A closed walk is a cycle except that it can repeat nodes and arcs. 12 More terminology 1 3 2 4 An undirected network is connected if every node can be reached from every other node by a path 5 1 3 2 4 5 13 A directed network is connected if it’s undirected version is connected. This directed graph is connected, even though there is no directed path between 2 and 5. On connectivity zThere are simple efficient procedures for determining if a graph is connected. 1 3 10 9 7 6 4 2 8 5 zHere is a graph with two components, that is maximally connected subgraphs. We will not describe these algorithms, but will do a more general algorithm later in this lecture 14 The Bridges of Koenigsberg: Euler 1736 z z “Graph Theory” began in 1736 Leonard Euler – Visited Koenigsberg – People wondered whether it is possible to take a walk, end up where you started from, and cross each bridge in Koenigsberg exactly once – Generally it was believed to be impossible 15 The Bridges of Koenigsberg: Euler 1736 A 1 2 3 B 5 4 C 6 7 D Is it possible to start in A, cross over each bridge exactly once, and end up back in A? 16 The Bridges of Koenigsberg: Euler 1736 A 1 2 3 B 5 4 C 6 7 D Conceptualization: Land masses are nodes 17 The Bridges of Koenigsberg: Euler 1736 A 1 2 3 B 5 4 6 D C 7 Conceptualization: Bridges are arcs 18 The Bridges of Koenigsberg: Euler 1736 A 1 2 3 B 5 4 6 D C 7 Translation to graphs or networks: Is there a walk starting at A and ending at A and passing through each arc exactly once? Why isn’t there such a walk? 19 Adding two bridges creates such a walk A 1 8 2 B 4 5 6 3 C 9 D 7 Here is the walk. A, 1, B, 5, D, 6, B, 4, C, 8, A, 3, C, 7, D, 9, B, 2, A 20 Note: the number of arcs incident to B is twice the number of times that B appears on the walk. Eulerian cycle: a closed walk that passes through each arc exactly once z Degree of a node = number of arcs incident to the node z Necessary condition: each node has an even degree. z Why necessary? The degree of a node j is twice the number of times j appears on the walk (except for the initial and final node of the walk.) Theorem. A graph has an eulerian cycle if and only if the graph is connected and every node has even degree. 21 Eulerian path: a walk that is not closed and passes through each arc exactly once Theorem. A graph has an eulerian path if and only if exactly two nodes have odd degree and the graph is connected. 22 Exercise: Does the graph below have an Eulerian path or cycle? If so, find it. 23 Eulerian cycles z z z 24 Eulerian cycles and extensions are used in practice Mail Carrier routes: – visit each city block at least once – minimize travel time – other constraints in practice? Trash pickup routes – visit each city block at least once – minimize travel time – other constraints in practice? More Definitions 1 3 2 4 A network is connected if if every node can be reached from every other node by a path 5 A spanning tree is a connected subset of a network including all nodes, but containing no cycles. 1 3 1 3 1 3 2 4 2 4 2 4 5 25 5 5 More on Trees z z An out-tree is a spanning tree in which every node has exactly one incoming arc except for the root. Theorem. In an out-tree, there is a directed path from the root to all other nodes. (All paths come out of the root). 1 1 3 2 4 5 2 4 7 12 26 3 5 8 6 9 13 10 11 The Shortest Path Problem 2 4 4 2 2 1 1 2 3 4 6 2 3 3 5 What is the shortest path from a source node (often denoted as s) to a sink node, (often denoted as t)? What is the shortest path from node 1 to node 6? Assumptions for this lecture: 1. There is a path from the source to all other nodes. 2. All arc lengths are non-negative 27 Shortest Path Problem z Where does it arise in practice? – Common applications • shortest paths in a vehicle • shortest paths in internet routing • shortest paths around MIT – Less obvious: close connection to dynamic programming which we will see in later lectures z 28 How will we solve the shortest path problem? – Dijkstra’s algorithm A surprising application: Finding optimal paragraph layouts TeX optimally decomposes paragraphs by selecting the breakpoints for each line optimally. It has a subroutine that computes the attractiveness F(i,j) of a line that begins at word i and ends at word j-1. How can one use F(i,j) to create a shortest path problem whose solution will solve the paragraph problem. Step 1. Assign numbers to the words TeX optimally decomposes paragraphs by ….. 1 2 3 4 5 29 will solve the paragraph problem. 48 49 50 51 52 “end” 53 On the values of F( ) The better the look of the line, the lower the value of F. The values below are illustrative, but are artificial. TeX 1 TeX 1 TeX 1 optimally 2 optimally 2 decomposes 3 F(1, 4) = 25 paragraphs 4 F(1, 5) = 3 TeX optimally decomposes paragraphs by 1 2 3 4 5 F(1, 6) = 1 30 optimally 2 decomposes 3 F(1, 3) = 50 F(1, j) = 10,000 for j > 6. The shortest path formulation Create a shortest path problem with nodes 1, 2, … , n+1 where the cost of arc (i, j) is f(i, j). TeX optimally decomposes paragraphs by selecting the breakpoints for each line optimally. It has a subroutine that computes the attractiveness F(i,j) of a line that begins at word i and ends at word j-1. How can one use F(i,j) to create a shortest path problem whose solution will solve the paragraph problem. Tex by 1 5 3 31F(1, 5) = 3 optimally computes of 1 12 2 18 4 22 .3 j-1 create will “end” 34 41 48 53 4 .5 0 The shortest path formulation Each path from 1 to 53 corresponds to a paragraph layout. The most beautiful layout is the shortest path. TeX optimally decomposes paragraphs by selecting the breakpoints for each line optimally. It has a subroutine that computes the attractiveness F(i,j) of a line that begins at word i and ends at word j-1. How can one use F(i,j) to create a shortest path problem whose solution will solve the paragraph problem. “end” Tex selecting optimally 1 32 1 6 1 12 .5 the word F(i,j) 19 28 39 .3 .3 solution “end” .8 47 53 0 Dijkstra’s Algorithm for the Shortest Path Problem 2 4 4 2 2 1 1 2 3 4 6 2 3 3 Exercise with your partner. Find the shortest paths by inspection. 5 Exercise: find the shortest path from node 1 to all other nodes. Keep track of distances using labels, d(i) and each node’s immediate predecessor, pred(i). d(1)= 0, pred(1)=0; d(2) = 2, pred(2)=1 Find the other distances, in order of increasing 33distance from node 1. Key observations z z z Suppose that d(i) is the length of some path from node 1 to node i. Suppose that there is an arc (i, j) of length cij. Then there is a path from node 1 to node j of length at most d(i) + cij. Path P 1 62 i 10 78 72 j If there are two paths from node 1 to node j, then the shortest path from i to j is at most the length of the shorter of these two paths. 34 A Key Procedure in Shortest Path Algorithms z At each iteration d(j) is the length of some path from node 1 to node j. (If no path is known, then d(j) = ∞) Procedure Update(i) for each (i,j) ∈ A(i) do if d(j) > d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i; Path P 1 62 i 10 78 j 72 Up to this point, the best path from 1 to j has length 78 But P, (i,j) is a path from 1 to j of length 72. 35 Dijkstra’s Algorithm begin d(s) : = 0 and pred(s) : = 0; d(j) : = ∞ for each j ∈ N - {s}; LIST : = {s}; while LIST ≠ ∅ do begin let d(i) : = min {d(j) : j ∈ LIST}; remove node i from LIST; update(i) if d(j) decreases from ∞, place j in LIST end end 36 Initialize distances. LIST = set of temporary nodes Select the node i on LIST with minimum distance label, and then update(i) Initialize d(2) = ∞ pred(2) = ∅ 2 d(1) = 0 pred(1) = ∅ 4 d(4) = ∞ pred(4) = ∅ 2 4 2 1 1 3 4 d(3) = ∞ pred(3) = ∅ d( ) = {0, 3 d(6) = ∞ pred(6) = ∅ 6 2 3 LIST = {1, 2 5 d(5) = ∞ pred(5) = ∅ d(2) = ∞ pred(2) = ∅ 2 2 4 d( ) = {0, { 3 d(6) = ∞ pred(6) = ∅ 6 2 d(3) = ∞ pred(3) = ∅ LIST = {{1, 2 3 4 3 38 2 1 11 d(1) = 0 pred(1) = ∅ 4 d(4) = ∞ pred(4) = ∅ Find the node i on LIST with minimum distance label. 5 d(5) = ∞ pred(5) = ∅ Remove i from LIST. Make i permanent. update(1) d(2) = ∞ 2 pred(2) = ∅ 1 d(4) = ∞ pred(4) = ∅ 4 2 2 d( d( )) == {{0, {2 2, 4 6 2 d(3) = ∞ 4 pred(3) = ∅ 1 LIST LIST == {{1, { 2, 3 2 3 4 3 39 2 1 11 d(1) = 0 pred(1) = ∅ 4 3 5 d(5) = ∞ pred(5) = ∅ d(6) = ∞ pred(6) = ∅ d(2) = ∞ 2 pred(2) = ∅ 1 2 d(1) = 0 pred(1) = ∅ 4 2 4 2 1 1 2 3 4 6 2 3 d(3) = 4 pred(3) = 1 LIST LIST == {{{1, 32, 3 40 d(4) = ∞ pred(4) = ∅ Find the node i on LIST with minimum distance label. d( d( )) == {{{0, 42 2, 4 3 d(6) = ∞ pred(6) = ∅ 5 d(5) = ∞ pred(5) = ∅ Remove i from LIST. Make i permanent. Update(2) d(4) = ∞ 6 pred(4) = ∅ 2 d(2) = 2 pred(2) = 1 2 d(1) = 0 pred(1) = ∅ 4 2 4 3 4 6 2 3 d(3) = 4 3 1 pred(3) = 2 LIST = { 3, 4 4, 5 41 2 1 1 2 d( ) = { 3 4 3, 6 6, 4 3 5 d(5) = ∞ 4 pred(5) = ∅ 2 d(6) = ∞ pred(6) = ∅ d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 Find the node i on LIST with minimum distance label. 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 6 2 33 d(3) = 3 pred(3) = 2 LIST = {4, { 3,54, 5 42 2 1 1 2 d( ) = {{6, 3,46, 4 3 d(6) = ∞ pred(6) = ∅ 5 d(5) = 4 pred(5) = 2 Remove i from LIST. Make i permanent. Update(3) d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 6 2 33 d(3) = 3 pred(3) = 2 LIST = {4, 5 43 2 1 1 2 d( ) = {6, 4 3 5 d(5) = 4 pred(5) = 2 d(6) = ∞ pred(6) = ∅ d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 Find the node i on LIST with minimum distance label. 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 6 2 3 d(3) = 3 pred(3) = 2 LIST = {4, {4 5 44 2 1 1 2 d( ) = {6 {6, 4 3 d(6) = ∞ pred(6) = ∅ 55 d(5) = 4 pred(5) = 2 Remove i from LIST. Make i permanent. Update(5) d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 6 2 3 d(3) = 3 pred(3) = 2 LIST = {4, {4 6 45 2 1 1 2 d( ) = {6 {6, 6 3 55 d(5) = 4 pred(5) = 2 d(6) = ∞ 6 pred(6) = ∅ 5 d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 1 1 2 3 4 6 2 3 d(3) = 3 pred(3) = 2 LIST = {4, {6 6 46 44 2 d( ) = {6 {6, 6 3 Find the node i on LIST with minimum distance label. d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 Remove i from LIST. Make i permanent. Update(4) d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 1 1 d( ) = {6 6 2 d(3) = 3 pred(3) = 2 LIST = {6 2 3 4 3 47 44 2 3 5 d(5) = 4 pred(5) = 2 d(6) = 6 pred(6) = 5 d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 Find the node i on LIST with minimum distance label. 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 d(3) = 3 pred(3) = 2 LIST = {{6 d( ) = {6 { 66 2 3 48 2 1 1 2 3 d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 Remove i from LIST. Make i permanent. Update(6) d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 d(3) = 3 pred(3) = 2 LIST = {{6 d( ) = {6 { 66 2 3 49 2 1 1 2 3 d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 Node 6 has no outgoing arcs. d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 Find the node i on LIST with minimum distance label. 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 d(3) = 3 pred(3) = 2 LIST = {{6 d( ) = {6 { 6 2 3 50 2 1 1 2 3 d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 LIST = ∅. The algorithm ends. The shortest path from node 1 to node 6. d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 d(3) = 3 pred(3) = 2 LIST = {{6 d( ) = {6 { 6 2 3 51 2 1 1 2 3 d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 Trace back the path from node 6 to node 1 using the predecessors. The shortest path from node 1 to node 6. d(4) = 6 pred(4) = 2 d(2) = 2 pred(2) = 1 4 2 d(1) = 0 pred(1) = ∅ 2 4 3 4 d(3) = 3 pred(3) = 2 LIST = {{6 d( ) = {6 { 6 2 3 52 2 1 1 2 3 d(6) = 6 pred(6) = 5 5 d(5) = 4 pred(5) = 2 The “predecessor” arcs form an out-tree rooted at node 1. Comments on Dijkstra’s Algorithm 53 z Dijkstra’s algorithm makes nodes permanent in increasing order of distance from the origin node. z Dijkstra’s algorithm is efficient in its current form. The running time grows as n2, where n is the number of nodes z It can be made much more efficient z In practice it runs in time linear in the number of arcs (or almost so). Summary z The Eulerian cycle problem z The shortest path problem z Dijkstra’s algorithm finds the shortest path from node 1 to all other nodes in increasing order of distance from the source node. z The bottleneck operation is identifying the minimum distance label. One can speed this up, and get an incredibly efficient algorithm 54 Some final comments 55 z The shortest path problem shows up again and again in network optimization z There is an interesting connection with dynamic programming z There are other solution techniques as well. We’ll see one in a later lecture.