CS计算机代考程序代写 algorithm Microsoft PowerPoint - CSE101 5 Graph Algorithms.pptx

Microsoft PowerPoint – CSE101 5 Graph Algorithms.pptx

O. Braun

1Graph Algorithms

Euler and Hamilton

O. Braun

2Graph Algorithms

Euler Tours

An Euler Tour of a graph is a path where each edge occurs exactly once.
 Euler Tours (when they exist) can be computed in polynomial time.

O. Braun

3Graph Algorithms

Euler Tours

Euler:
a) There are only even‐degree vertices  Euler circuit
b) There are exactly two odd‐degree vertices  Euler path
c) There are three or more odd‐degree vertices  neither Euler circuit

nor Euler path

Finding an Euler circuit or an Euler path is fast and in solvable polynomial time
(Fleury‘s algorithm, published in 1883).

Rosen
Ch. 10.5

O. Braun

4Graph Algorithms

Euler Tours: Fleury‘s algorithm

There are only even‐degree vertices  Euler circuit

• Fleury‘s algorithm constructs Euler circuits by first choosing an arbitrary vertex of a
connected multigraph, and then forming a circuit by choosing edges successively.

• Once an edge is chosen, it is removed.

Rosen
Ch. 10.5

O. Braun

5Graph Algorithms

Euler Tours: Fleury‘s algorithm

There are exactly two odd‐degree vertices  Euler path

• Fleury‘s algorithm constructs Euler paths by first choosing a vertex with odd degree
of a connected multigraph, and then forming a path by choosing edges successively.

• Once an edge is chosen, it is removed.
• Edges are chosen successively so that each edge begins where the last edge ends,

and so that this edge is not a bridge unless there is no alternative.

Bridge:
Removing (4,5)
from Gwould
cause G to be
disconnected.

Rosen
Ch. 10.5

O. Braun

6Graph Algorithms

Hamilton Tours

A Hamilton Tour of a graph is a path where each vertex occurs exactly once.
 Travelling Salesperson Problem (TSP)

The best algorithms known for finding a Hamilton circuit in a graph or determining that no
such circuit exists have exponential worst-case time complexity (in the number of the
vertices of the graph). The problem is NP-complete.

Remember: A path is a cycle if it is a circuit that does not repeat vertices. The more precice
name would therefore be Hamilton cycle.

Draw a graph
with a Hamiltonian cycle
but no Euler circuit.

Draw a graph
with an Euler circuit
but no Hamiltonian cycle. Rosen

p. 698

O. Braun

7Graph Algorithms

Graph Search

BFS and DFS

O. Braun

8Graph Algorithms

Distance

A
s

D
E

O. Braun

9Graph Algorithms

BFS: algorithm

eject = de-queue

inject = en-queue

A
s

D
E

s dist = 0
A B dist = 1
C E D dist = 2

empty

O. Braun

10Graph Algorithms

Correctness of BFS

Loop Invariant: For each d=0, 1, 2, …. there is a moment after an iteration through the while-loop, at
which
(1) all nodes at distance < d from s have their distances correctly set (2) all other nodes have their distances set to infinity (3) the queue contains exactly the nodes at distance d. Proof (by induction): Induction Base: d=0, dist(s)=0. Inductive Hypothesis: same as Loop Invariant for d-1. Inductive Step: During the d-th run through the while-loop, vertex u with distance d-1 from s is ejected. Among all adjacent vertices v of u, only those with dist(v)=infinity are injected and the distance of these vertices is set to dist(v) = dist(u)+1 = d-1 + 1 = d. O. Braun 11Graph Algorithms BFS (Directed Graphs): Runtime eject = de-queue inject = en-queue n n=|V|, m=|E| n initialization n injections n ejections n increasing distance values m look at each edge exactly one time  O(n+m) • Solution Tree: each edge in this tree corresponds to an edge in the graph • What about the vertices? • Solution Tree: B appears twice as there are two paths to B. • Each vertex is exactly 1x injected and 1x ejected. m n n n O. Braun 12Graph Algorithms BFS: Shortest Path Tree inject = en-queue Question: Is there a way to output the dist-values and the shortest path tree? eject = de-queue prev(v)=u O. Braun 13Graph Algorithms Breadth First Search BFS( G, s ) 1. u=s; 2. Mark all adjacent vertices v of vertex u „in lexicographic order“ from left to right (mark a vertex only if it hasn‘t been marked already). 3. Repeat Step 1 until all vertices have been marked. K C EM B D s T P O. Braun 14Graph Algorithms Depth First Search Depth First Search (DFS) is a method to explore a graph in a systematic way. DFS has been popularized by Robert Tarjan (Depth‐first search and linear graph algorithms, SIAM Journal on Computing 1 (1972), 146‐160). N O T E : (HERE) DIRECTED GRAPHS! procedure DFS(G) t=0; for all uV do if color(u)=white then DFS-Visit; procedure DFS-Visit(u) color(u)=gray; t++; d[u]=t; for all vV with (u,v)E do if color(v)=white then DFS-Visit(v); color(u)=black; Correctness. Find the loop invariant and prove the correctness of DFS(G). Time Analysis. The running time of DFS(G) is O(n+m). (left as an Exercise) (left as an Exercise)Note: recursive Stack! O. Braun 15Graph Algorithms Depth First Search DFS( s ) 1. u=s; 2. Mark the „neighbor vertex“ v of vertex u „with the smallest number“ (if it hasn‘t been marked already). 3. Repeat Step 1 until all vertices have been marked. K C EM B D T P s O. Braun 16Graph Algorithms DFS and BFS • determine if a graph has a circuit • find strongly connected components of a directed graph • find what vertices can be reached by a given vertex • find a spanning tree of a graph • find a path from a vertex s to a vertex v • carry out a topological sort of a graph • find sinks and sources in directed acyclic graphs • DFS is not good for finding shortest distances between vertices • BFS does not restart at other connected components since all vertices not connected to the starting vertex are distance infinity away O. Braun 17Graph Algorithms Minimum Spanning Trees O. Braun 18Graph Algorithms Minimum Spanning Trees: Motivation • Imagine you have a business with several offices and you want to lease phone lines to connect them up with each other. • The phone company charges different amounts of money to connect different pairs of cities. • You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn’t a tree you can always remove some edges and save money. • In general, you can replace “phone lines” by something like electrical, hydraulic, TV cable, computer, road, water pipes and so on. • Minimum Spanning Trees play a crucial role in Network design. O. Braun 19Graph Algorithms Spanning Trees: Definition Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex in G. Find a spanning tree of the simple graph G: O. Braun 20Graph Algorithms Spanning Trees: Definition Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex in G. Find a spanning tree of the simple graph G: O. Braun 21Graph Algorithms Minimum Spanning Trees: Definition Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex in G. A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges. O. Braun 22Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 4 34 2 5 4 5 6 Start T B S K M N O. Braun 23Graph Algorithms Minimum Spanning Trees Prim‘s algorithm T B S K M N 3 4 4 34 2 5 4 5 6 2 O. Braun 24Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 4 34 2 5 4 5 6 2+3 T B S K M N O. Braun 25Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 4 34 2 5 4 5 6 2+3+3 T B S K M N O. Braun 26Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 4 34 2 5 4 5 6 2+3+3+4 T B S K M N Start vertex K comes lexicographically before M. O. Braun 27Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 4 34 2 5 4 5 6 2+3+3+4+4 =16 T B S K M N O. Braun 28Graph Algorithms Minimum Spanning Trees Prim‘s algorithm 3 4 3 2 4 2+3+3+4+4 =16 T B S K M N O. Braun 29Graph Algorithms Minimum Spanning Trees: Literature Computing a minimum spanning tree in an undirected network has been already described in 1926 by Boruvka who also gave a first solution. We described an algorithm that is known as Prim‘s algorithm (R.C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J. 36 (1957), 1389-1401, and E.W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959), 269-271). Prim‘s algorithm has been already detected by Jarnik (V. Jarnik, O jistem problemu minimalnim, Praca Moravske Prirodovedecke Spolecnosti 6 (1930), 57-63). Another popular algorithm for computing minimum spanning trees is due to Kruskal (J.B. Kruskal, Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7 (1956), 48-50). Prim‘s and Kruskal‘s algorithms are examples of greedy algorithms (that decide only with the help of easy and local optimality criteria). O. Braun 30Graph Algorithms Minimum Spanning Tree: Running time analysis Remember that n=|V| and m=|E|. Prim‘s algorithm needs running time O(n log n + m) if the priority queue (that is needed to keep track of the nodes that are not yet included in the minimum spanning tree) is implemented with e.g. a Fibonacci-Heap. Kruskal‘s algorithm needs running time O(m log m) (because the edges have to be sorted). Which algorithm is better, i.e. needs less time? Remember … m < n(n-1)/2 But it depends … 1. The number m of edges (in reasonable problem settings) can range from about n to n(n-1)/2. We must take that into consideration when we analyze the running times. 2. If the edge costs are not arbitrary but e.g. small integers that can be sorted in linear time, then Kruskal‘s algorithm needs only O(n+m (n, m/n)), almost linear time. [α is the extremely slowly growing inverse of the Ackermann function] O. Braun 31Graph Algorithms Topological Sorting O. Braun 32Graph Algorithms Topological Sorting Applications: • Project Management • Shortest Paths in Networks Precondition: • directed graphs that have no cycles are called directed acyclic graphs, or DAGs • every DAG has a source s • G is a DAG if and only if G–s is a DAG Topological Ordering: • In a topological ordering, it must be true that for every edge v →w, v comes before w in the ordering. A must be finished before B starts and so on. Can this project be accomplished? Whenever there's a cycle, we can't find a prerequisite ordering. O. Braun 33Graph Algorithms Topological Sorting The following algorithm is first described by Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM 5: 558–562. A DFS procedure is described by Tarjan, Robert E. (1976), "Edge‐disjoint spanning trees and depth‐first search", Acta Informatica 6: 171–185. procedure TopSort(G) L := empty list that will contain the sorted elements; S := set of all nodes with no incoming edge; while S is not empty do remove a node u from S and add it to L; for all (u,v) do remove edge (u,v) from the graph if indegree(v)=0 then insert v into S; if there exists any remaining edge in the graph G return “no topological sort, G has at least one cycle”; else return L; // a topologically sorted order Implementation: • Maintain an integer array, InDegree[ ], where for each i between 1 and n, InDegree[i] is the number of incoming edges to vertex i. • Maintain a list of sources, S, either a stack or a queue. O. Braun 34Graph Algorithms TopSort: Example Activities: 9 Dependencies: A: Building Walls A before B, C, D, E B: Roof Timbering B before C, D, E C: Roof Tiling C before D, E D: Rendering inside E: Rendering outside C E B A D O. Braun 35Graph Algorithms TopSort: Example Activities: 9 Dependencies: A: Building Walls A before B, C, D, E B: Roof Timbering B before C, D, E C: Roof Tiling C before D, E D: Rendering inside E: Rendering outside C E B A D O. Braun 36Graph Algorithms TopSort: Example Activities: 9 Dependencies: A: Building Walls A before B, C, D, E B: Roof Timbering B before C, D, E C: Roof Tiling C before D, E D: Rendering inside E: Rendering outside C E B A D O. Braun 37Graph Algorithms TopSort: Example O. Braun 38Graph Algorithms TopSort: Example O. Braun 39Graph Algorithms Single‐Source Shortest Paths O. Braun 40Graph Algorithms Single‐source shortest paths Find the shortest paths from a single source s to all other vertices in the network. (v) = (s,v) = costs (length) of the shortest path from the source s to v: distance from s to v O. Braun 41Graph Algorithms Formal description O. Braun 42Graph Algorithms Bellman / Dijkstra / Ford / Moore Richard Ernest Bellman (1920-1984, 63) New York City, New York - Los Angeles, California Dynamic Programming RAND Corporation, Univ. of Southern California Edsger Wybe Dijkstra (1930-2002, 72) Rotterdam – Nuenen (Netherlands) systems scientist, programmer, software engineer, UT Austin three children Lester Randolph Ford, Jr. (1927-2017, 89) Houston, Texas - Santa Barbara, California network flow problems married twice, nine children Edward Forrest Moore (1925-2003, 77) Baltimore, Maryland, - Madison, Wisconsin 1951-1956 Bell Labs one of the founders of automata theory (Moore machines) three daughters O. Braun 43Graph Algorithms Single Source Shortest Paths Question: Is it always possible to find a shortest path between two vertices in a directed graph? Find two possibilities where you actually cannot find a shortest path between two vertices. O. Braun 44Graph Algorithms Single Source Shortest Paths Question: Is it always possible to find a shortest path between two vertices in a directed graph? Find two possibilities where you actually cannot find a shortest path between two vertices. 1. There is no path from s to v. 2. The path from s to v contains a negative cycle. O. Braun 45Graph Algorithms Single Source Shortest Paths O. Braun 46Graph Algorithms initialize and relax Note: initialize and relax are used by all of the three algorithms Notation: d[v] is the length of a path from s to v, d[s]=0. O. Braun 47Graph Algorithms Bellman/Ford Bellman/Ford O. Braun 48Graph Algorithms Historical Background O. Braun 49Graph Algorithms Bellman/Ford O. Braun 50Graph Algorithms Example 1: Initialization O. Braun 51Graph Algorithms Example 1: Phase 1 Consider only these vertices a as start vertices of relax (a,b) where the distance value of a has changed in the previous phase. O. Braun 52Graph Algorithms Example 1: Phase 2 Consider only these vertices a as start vertices of relax (a,b) where the distance value of a has changed in the previous phase. O. Braun 53Graph Algorithms Example 1: Phase 3 Consider only these vertices a as start vertices of relax (a,b) where the distance value of a has changed in the previous phase. O. Braun 54Graph Algorithms Example 1: Phase 4 Consider only these vertices a as start vertices of relax (a,b) where the distance value of a has changed in the previous phase. O. Braun 55Graph Algorithms Correctness Loop Invariant: After k iterations, the current distance values of all vertices that are at most k steps away from s are computed correctly. Current distance values because a vertex might be visited again after l > k iterations.

Why are n-1 iterations sufficient?
• We won‘t run through a positive cycle on a shortest path (i.e. a shortest path is simple).
• Given that there are no negative cycles, there are at most n-2 vertices on a shortest path

from the source s to another vertex u.

O. Braun

56Graph Algorithms

Negative cycles

If the distance value of a node changes in phase n, then there must be a negative cycle.

 Bellman/Ford can detect negative cycles.

 Just let it run for one more iteration and look if a distance value changes.

O. Braun

57Graph Algorithms

Example 2

O. Braun

58Graph Algorithms

Example 2

O. Braun

59Graph Algorithms

Dynamic Programming approach

(Kleinberg/Tardos, Ch. 6.8)

O. Braun

60Graph Algorithms

Dijkstra for non‐negative networks

Dijkstra

O. Braun

61Graph Algorithms

Dijkstra (for non‐negative networks)

O. Braun

62Graph Algorithms

Example 1

O. Braun

63Graph Algorithms

Example 1

O. Braun

64Graph Algorithms

Example 1: Initialization

O. Braun

65Graph Algorithms

Example 1: Phase 1

Consider only these vertices a as
start vertices of relax (a,b)
where the distance value of a is
minimal to the start vertex s.

O. Braun

66Graph Algorithms

Example 1: Phase 2

Consider only these vertices a as
start vertices of relax (a,b)
where the distance value of a is
minimal to the start vertex s.

O. Braun

67Graph Algorithms

Example 1: Phase 3

Consider only these vertices a as
start vertices of relax (a,b)
where the distance value of a is
minimal to the start vertex s.

O. Braun

68Graph Algorithms

Example 1: Phase 4

Consider only these vertices u as
start vertices of relax (a,b)
where the distance value of a is
minimal to the start vertex s.

O. Braun

69Graph Algorithms

Example 2

O. Braun

70Graph Algorithms

Example 2

O. Braun

71Graph Algorithms

Example 2

O. Braun

72Graph Algorithms

Example 2

O. Braun

73Graph Algorithms

Dijkstra: Running Time

initialize n x search and m x relax (u,v) Total Time m=n m=n2

delete the min. and possibly
of < n numbers decrease distance values Priority Queue (makequeue) (deletemin) (decreasekey) Array O(n) n O(n) m O(1) O(n2+m) O(n2) O(n2) [Dijkstra 1959] Binary Heap O(n) n O(log n) m O(log n) O((n+m) log n) O(n log n) O(n2 log n) [Williams 1964] Fibonacci Heap O(n) n O(log n) m O(1) O(n log n + m) O(n log n) O(n2) [Fredman/Tarjan 1987] O. Braun 74Graph Algorithms Dijkstra: Correctness Loop Invariant: After k iterations, the final distance values of all vertices that are at most k steps away from s are computed correctly. 1. Among all possible paths from s to v we always keep only the (so far) shortest path from s to v. 2. When we select a vertex v that has minimal distance from s, then there might still be another path to v, but never with a smaller distance (all edges have non-negative costs!). Literature: Dasgupta/Papadimitriou/Vazirani Ch. 4.4 Kleinberg/Tardos, Ch. 5.4 O. Braun 75Graph Algorithms Bellman for acyclic networks Bellman O. Braun 76Graph Algorithms Bellman (for acyclic networks) O. Braun 77Graph Algorithms Bellman: Example 1 O. Braun 78Graph Algorithms Bellman: Example 1 TopSort O. Braun 79Graph Algorithms Bellman: Example 2 O. Braun 80Graph Algorithms Bellman: Example 2 A {B,E} {C, F, I} {D,G} H TopSort O. Braun 81Graph Algorithms Bellman: Running time • Topological sort costs O(n+m) • In each iteration the next vertex in the topological sort is selected and in total m edges are relaxed.  O(n+m) O. Braun 82Graph Algorithms Bellman: Correctness Loop Invariant: After k iterations, the final distance values of all vertices that are at most k steps away from s are computed correctly. 1. Among all possible paths from s to v we always keep only the (so far) shortest path from s to v. 2. When you select a vertex v that comes next in the topological order, you can be sure that there won‘t be another path to v that you didn‘t have already considered. O. Braun 83Graph Algorithms Bellman: Correctness Question: Why is the rule „continue at that vertex v that comes next in the topological order“ always optimal? Answer: 1. Among all possible paths from s to v you always keep only the (so far) shortest path from s to v. 2. When you select a vertex v that comes next in the topological order, you can be sure that there won‘t be another path to v that you didn‘t have already considered. O. Braun 84Graph Algorithms All‐Pairs Shortest Paths O. Braun 85Graph Algorithms Shortest‐Path‐Algorithms Pre-condition for SSSP/APSP: no negative cycles on the path from s to v. n = number of vertices m = number of edges SSSP: m=(n) m=(n2) BFS unweighted or cij=1 O(n+m) O(n) O(n2) Bellman acyclic O(n+m) O(n) O(n2) Dijkstra non-negative O(nlogn+m) O(nlogn) O(n2) Bellman/Ford general case O(nm) O(n2) O(n3) APSP: m=(n) m=(n2) BFS all weights = 1 O(n2+nm) O(n2) O(n3) Bellman acyclic O(n2+nm) O(n2) O(n3) Dijkstra non-negative O(n2logn+nm) O(n2logn) O(n3) Bellman/Ford general case O(n2m) O(n3) O(n4) Floyd/Warshall O(n3) O(n3) O(n3) Johnson O(n2logn+nm) O(n2logn) O(n3) O. Braun 86Graph Algorithms Floyd‐Warshall for All Pairs Shortest Paths Floyd-Warshall O. Braun 87Graph Algorithms All-pairs shortest paths Find the shortest paths from every vertex to every other vertex. The Floyd-Warshall algorithm (also known as Floyd's algorithm, the Roy-Floyd algorithm, the Roy-Warshall algorithm) is an algorithm for efficiently and simultaneously finding the shortest paths between every pair of vertices in a network. Floyd’s algorithm is essentially equivalent to the transitive closure algorithm independently discovered by Roy (1959) and Warshall (1962), which is the reason it is associated with all three authors. Floyd, R. W., Algorithm 97, Comm. ACM 5-6, 345, 1962 Roy, B., Transitivité et connexité, C. R. Acad. Sci. Paris 249, 216-218, 1959 Warshall, S., A Theorem on Boolean Matrices, J. ACM 9, 11-12, 1962 O. Braun 88Graph Algorithms Floyd‐Warshall‐Algorithm O. Braun 89Graph Algorithms Idea for a Dynamic Programming ‐ algorithm The principle of the Floyd-Warshall-Algorithm is Dynamic Programming. Idea: Is the shortest path over a third vertex k shorter than the currently shortest path from i to j? Recurrence: dij (k-1) = distance of the shortest path from i to j whose intermediate vertices are in the set {1, 2, …, k-1} dij (0) = c(i,j) dij (k) = min{dij (k-1) ; dik (k-1)+dkj (k-1)} j k vertices 1, ... , k-1i O. Braun 90Graph Algorithms Distance Matrix D0 O. Braun 91Graph Algorithms k=A from C to A (3) from A to B (3) from C to B (6) better than infinity ‐> update
from A to D (6) from C to D (9) better than infinity ‐> update

6 9

O. Braun

92Graph Algorithms

k=B

from A to B (3) from B to D (2) from A to D (5) better than 6 ‐> update
from B to E (4) from A to E (7) better than infinity ‐> update

O. Braun

93Graph Algorithms

k=B

from A to B (3) from B to D (2) from A to D (5) better than 6 ‐> update
from B to E (4) from A to E (7) better than infinity ‐> update

from C to B (6) from B to D (2) from C to D (8) better than 9 ‐> update
from B to E (4) from C to E (10) better than infinity ‐> update

O. Braun

94Graph Algorithms

k=C

from D to C (1) from C to A (3) from D to A (4) better than infinity ‐> update
from C to B (6) from D to B (7) better than infinity ‐> update
from C to D (8) from D to D (9) not better than 0
from C to E (10) from D to E (11) not better than 1

O. Braun

95Graph Algorithms

k=D

from A to D (5) from D to A (4) from A to A (9) not better than 0
from D to B (7) from A to B (12) not better than 3
from D to C (1) from A to C (6) better than infinity ‐> update
from D to E (1) from A to E (6) better than 7 ‐> update

O. Braun

96Graph Algorithms

k=D

from B to D (2) from D to A (4) from B to A (6) better than infinity ‐> update
from D to B (7) from B to B (9) not better than 0
from D to C (1) from B to C (3) better than infinity ‐> update
from D to E (1) from B to E (3) better than 4 ‐> update

O. Braun

97Graph Algorithms

k=D

from C to D (8) from D to A (4) from C to A (12) not better than 3
from D to B (7) from C to B (15) not better than 6
from D to C (1) from C to C (9) not better than 0
from D to E (1) from C to E (9) better than 10 ‐> update

O. Braun

98Graph Algorithms

k=E

E is a sink. Obviously, we can omit checking sinks (as there are no outgoing arrows) and
sources (as there are no incoming arrows).

O. Braun

99Graph Algorithms

Example Problem

O. Braun

100Graph Algorithms

Literature

• Dasgupta/Papadimitriou/Vazirani, Ch. 4.4, Ch. 6.6
• Kleinberg/Tardos, Ch. 5.4, Ch. 6.8
• Cormen/Leiserson/Rivest/Stein, Ch. 24, Ch. 25
• Johnsonborough/Schaefer, Ch.7.4

O. Braun

101Graph Algorithms

Travelling Salesperson Problem

O. Braun

102Graph Algorithms

Travelling Salesperson problem (TSP)

Given a list of cities and the distances
between each pair of cities:
What is the shortest possible route that
visits each city exactly once and returns
to the origin city?

• There are n=9 vertices and therefore
8!/2 possible roundtrips (starting and
ending at O).

• TSP is NP-hard.

We consider the metric TSP where the intercity distances satisfy the triangle inequality.
A very natural restriction of the TSP is to require that the distances between cities form a
metric to satisfy the triangle inequality.

The direct connection from A to C is never farther than the route via intermediate B.

O. Braun

103Graph Algorithms

Minimum Spanning Tree (MST) – Heuristic

MST:

O. Braun

104Graph Algorithms

Minimum Spanning Tree (MST) – Heuristic

Euler-Tour:
5 1 2 2 3 3 4 4 2 1 1 2 1 2 2 5

O ‐>E ‐>F ‐>A ‐>F ‐>B ‐>F ‐>C ‐>F ‐>D ‐>H ‐>D ‐>F ‐>E ‐>G ‐>E ‐>O

O. Braun

105Graph Algorithms

Minimum Spanning Tree (MST) – Heuristic

Euler-Tour with Shortcuts:
5 1 2 2 3 3 4 4 2 1 1 2 1 2 2 5  = 40

O ‐>E ‐>F ‐>A ‐>F ‐>B ‐>F ‐>C ‐>F ‐>D ‐>H ‐>D ‐>F ‐>E ‐>G ‐>E ‐>O
O ‐>E ‐>F ‐>A ‐> B ‐> C ‐> D ‐>H ‐> G ‐> O

5 1 2 4 6 5 1 5 7  =36

O. Braun

106Graph Algorithms

Capacitated Vehicle Routing
Planning Problem

O. Braun

107Graph Algorithms

Problem description and background

The Capacitated Vehicle Routing Problem (CVRP) is one of the fundamental problems in
combinatorial optimization with a number of practical applications in transportation,
distribution and logistics. The aim of CVRP is to find a set of minimum total cost routes for
a fleet of capacitated vehicles based at a single depot, to serve a set of customers under the
following constraints:
(1) each route begins and ends at the depot,
(2) each customer is visited exactly once,
(3) the total demand of each route does not exceed the capacity of the vehicle.
The first mathematical formulation and algorithm (based on Linear Programming) for the
solution of the CVRP was proposed by Dantzig and Ramser in 1959:
Dantzig, G. B., Ramser, J. H. (1959). The truck dispatching problem. Management Science
6, 80-91.
Five years later, Clarke and Wright proposed the first heuristic to solve the CVRP-problem
(“Savings-heuristic”):
Clarke, G., Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number
of delivery points. Operations Research 12, 568-581.

O. Braun

108Graph Algorithms

Problem description and background

Many solution methods for the CVRP have been published. General surveys can be found
here:
Toth, P., Vigo, D. (2014). Vehicle routing: Problems, Methods and Applications, SIAM,
Second Edition.
Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science 43, 408-416.

The CVRP belongs to the category of NP-hard problems (it is a generalized version of the
Travelling Salesperson Problem (TSP)). Therefore, researchers have concentrated on
developing heuristic algorithms to solve this problem. Laporte et al. give an overview on
that:
Laporte, G.,Ropke, S., Vidal, T. (2014). Heuristics for the vehicle routing problem.
Vehicle routing: Problems, Methods and Applications, SIAM, Second Edition.

O. Braun

109Graph Algorithms

Formal problem description

O. Braun

110Graph Algorithms

Round‐trips

All-pairs shortest paths:

Round-trips:
OAO 14
OBO 18
OCO 20
ODO 16
OEO 10
OFO 12
OGO 14
OHO 18

122

O. Braun

111Graph Algorithms

Savings

Tour 1

Tour 2

Combined
tour:

O A O

OBO

7 7

9 9

OB9 9

O O77

Total distance:
(7+7)+
(9+9)=32 miles

Total distance:
7+4+9=20 miles
Savings:
7+9-4=12 miles

O. Braun

112Graph Algorithms

Example problem: Savings‐values

All-pairs shortest paths:

Savings-values:

O. Braun

113Graph Algorithms