The second problem that we will consider for networks is that of finding the shortest route between any two vertices in the network. As the name suggests the shortest route problem is most commonly applied to transport networks. Other applications include, for example, cost minimisation. Although there are a number of algorithms that are designed to find minimum cost routes between vertices in a network the only algorithm with which you need to be familiar at A Level is Dijkstra’s algorithm.
Graphs & Networks
Description of the graphs and networks category.
Dijkstra’s Algorithm
Dijkstra’s algorithm generates the shortest path tree from a given node to any (or every) other node in the network.
Although the problem that we will use as an example is fairly trivial and can be solved by inspection, the technique that we will use can be applied to much larger problems.
Dijkstra’s algorithm requires that each node in the network be assigned values (labels). There is a working label and a permanent label, as well as an ordering label. Whilst going through the steps of the algorithm you will assign a working label to each vertex. The smallest working label at each iteration will become permanent.
The steps of Dijkstra’s algorithm are:
- Give the start point the permanent label of 0, and the ordering label 1.
- Any vertex directly connected to the last vertex given a permanent label is assigned a working label equal to the weight of the connecting edge added to the permanent label you are coming from. If it already has a working label replace it only if the new working label is lower.
- Select the minimum current working value in the network and make it the permanent label for that node.
- If the destination node has a permanent label go to step 5, otherwise go to step 2.
- Connect the destination to the start, working backwards. Select any edge for which the difference between the permanent labels at each end is equal to the weight of the edge.
It is a good idea to use a system for keeping track of the current working labels and the ordering and permanent labels of each of the nodes in the network. A standard system found on A Level exams is that a small grid is drawn near each of the nodes, working labels are written in the lower box, ordering labels in the upper left box, and permanent labels in the upper right box, as shown in figure 1.
Example
In this example we will consider the network in figure 2. We would like to find the shortest path from node A to node H.
As you can see at the end of the video, the destination node (node H) has a permanent label. This means that a shortest route from A to H has been found.
The shortest route is found by tracing back from the destination node (node H) to the start (node A), selecting each edge for which the difference between permanent values at its terminating nodes is equal to the weight of the edge. The shortest routes for this network are shown in figure 3 below. The edges shown in green (AB and BC) are an alternative to the edge AC shown in red. In this case there are two equivalent shortest routes from A to H.
The solution to the shortest route problem, from A to H, in this network is therefore A-C-G-H, or the equivalent distance A-B-C-G-H. Both have a total distance of 11 units, given by the permanent label of the terminal node.
Critical Path Analysis – Introduction
Critical path analysis allows you to determine the best way of arranging activities. The typical question to answer is “what is the minimum time required for a process?”
Performing activities one after the other as you come to them might not be the best way of organising a project. If more than one activity can be worked on at the same time you will need to decide when to start each one. Below, in table 1, are the activities needed to build a house with durations given in days. We are going to perform a critical path analysis on the process of house construction.
| Task | Description | Duration |
|---|---|---|
| A | Excavate foundations | 2 |
| B | Pour concrete | 1 |
| C | Build walls | 3 |
| D | Construct roof sections | 7 |
| E | Put up roof sections | 1 |
| F | Tile roof | 3 |
| G | Install plumbing | 4 |
| H | Install electrics | 3 |
| I | Install windows and doors | 2 |
| J | Paint ceilings | 2 |
| K | Paint walls | 3 |
| L | Lay carpets | 2 |
The first thing that we need to do is to decide which of the activities depend on other activities:
- B requires that A be complete.
- C requires that B be complete.
- E requires that C and D be complete.
- F requires that E be complete.
- G, H, and I all require that F be complete.
- J and K require that G, H, and I be complete.
- L requires that J and K be complete.
With this information we can draw an activity network. In an activity network the edges represent activities, such as those listed above. The nodes represent events. An event is the start and/or finish of one or more activities. The activity network for the house building example is shown in figure 1.
The activity network shows that there are 12 events involved in the building of this house, and that 12 activities (plus 3 dummy activities) are required before the house is complete.
As you can see, there are a few activities that can occur concurrently. Later we will use this example to find the critical path through the operation (finding a critical path). It is the longest path and determines the minimum length of time that is necessary to complete the house.
Activity Networks
As we saw in the introduction to critical path analysis, an activity network is a graphical representation of activities and events that are needed for a process. There are several rules that have to be obeyed when creating accurate networks.
These rules are:
- An edge is used to represent an activity.
- A vertex represents an event, which is the start or end of one or more activities.
- Events are numbered so that the activity ends at a higher numbered event than it started.
- Events are numbered so that no activity starts and ends at the same event. An activity can therefore be uniquely identified by its start and end events.
- In order to avoid ambiguity between activities you must use ‘dummy’ activities. These are activities that have zero length and are inserted to ensure that precedence requirements are met. They allow two activities that ought to have the same start and end events to be distinguished.
- There should only be one start event and one finish event.
- The activity detail (or code) and duration are written along the edges.
- The edge length has no meaning.
Using these rules you should be able to create activity networks for any process that involves more than one activity.
Earliest and Latest Times
Once you have drawn out an activity network the next step is to work out the earliest and latest possible times for each event. This will let you find the minimum time necessary for the tasks to be completed taking activity precedence into account.
In order to make the identification of earliest and latest times easier, they are often put into a pair of boxes. The left box will be the earliest time and the right box will be the latest time. When working out the earliest times for each event you must start at the first event and assign an earliest time of 0. Work through each event in turn. Add the duration of the activity to the earliest time of the start event to get the earliest time of the end event. If there is more than one way of arriving at the end event then take the largest value for the earliest time.
Once you have gone through the entire network assigning earliest times you can begin to work out the latest times. This is done by starting at the last event and working backwards though the network. To start the process let the latest time of the last event be equal to the earliest time of that event. By subtracting the duration of an activity from the event that it ends at you will be able to find the latest time for the start event for that activity. If there is more than one way to arrive at a start event then take the smallest value for the latest time.
By looking at the earliest / latest times for the last event you will know the minimum duration for the overall process.
Allocating Resources
Once you have decided on the critical path for an activity network you will need to allocate resources to each task.
Resources could take the form of equipment, people, money, or any number of other things. Most often we will use people. The question you need to ask yourself is “how many people do I need so that the project can be finished without any delay?” In answering this question you are halfway to allocating resources.
In the example we have been looking at, there are at most three things that can be happening at any one time. Do we need to use three people, or will two people be enough (have we got enough time to complete H and I before G is completed)? Looking at the activity network we can see that there will not be enough time to do this.
Another way of showing the resources needed is to draw a cascade chart and then a resource histogram.
The cascade chart in figure 2 shows the critical path on the lower row and has a row for each of the other activities, starting at their earliest time and showing float at the end. This allows the viewer to see where activities can be collapsed down to be allocated to a single worker. The collapsed form, as a resource histogram, is shown in figure 3.
