Consider the following shortest path problem involving six cities with distances given in the table below:

Camino	Distance
City 1 to City 2	3
City 1 to City 3	2
City 2 to City 4	4
City 2 to City 5	5
City 3 to City 4	3
City 3 to City 5	7
City 4 to City 6	6
City 5 to City 6	2

1. Draw a network diagram for this problem.

2. Formulate the linear program that would find the shortest distance from City 1 to City 6.

3. What is the optimal solution: which paths should be traveled and what is the distance between City 1 and City 6?