Algorithms

Bubble Sort Algorithm

Step 1: If there is only one number in the list then stop.

Step 2: Make one pass down the list, comparing numbers in pairs and swapping as necessary.

Step 3: If no swaps have occurred then stop. Otherwise, ignore the last element of the list and return to Step 1.

2) Shuttle Sort Algorithm

1st Pass: Compare the 1st and 2nd numbers in the list and swap if necessary.

2nd Pass: Compare the 2nd and 3rd numbers in the list and swap if necessary. If a swap has occurred, compare the 1st and 2nd numbers and swap if necessary.

3rd Pass: Compare the 3rd and 4th numbers in the list and swap if necessary. If a swap has occurred, compare the 2nd and 3rd numbers, and so on up the list.

And so on, through the entire list.

3) First-Fit Algorithm

Place each object in turn in the first available space in which it will fit.

4) Prim’s Algorithm	To find a minimum spanning tree T:

Step 1: Select any node to be the first node of T.

Step 2: Consider the arcs which connect nodes in T to nodes outside T. Pick the one with minimum weight. Add this arc and the extra node to T. (If there are two or more arcs of minimum weight, choose any one of them.)

Step 3: Repeat Step 2 until T contains every node of the graph.

5) Kruskal’s Algorithm	To find a minimum spanning tree for a connected graph with n nodes:

Step 1: Choose the arc of least weight.

Step 2: Choose from those arcs remaining the arc of least weight which does not form a cycle with already chosen arcs. (If there are several such arcs, choose one arbitrarily.)

Step 3: Repeat Step 2 until n – 1 arcs have been chosen.

6) The Matrix Formulation of Prim’s Algorithm	To find a minimum spanning tree T:

Step 1: Select any node to be the first node of T.

Step 2: Circle the new node of T in the top row, and cross out the row corresponding to this new node.

Step 3: Find the smallest weight left in the columns corresponding to the nodes of T, and circle this weight. Then choose the node whose row the weight is in to join T. (if there are several possibilities for the weight, choose any one of them.)

Step 4: Repeat Steps 2 and 3 until T contains every node.

7) Dijkstra’s Algorithm

Step 1: Label the start node with zero and box this label.

Step 2: Consider the node with the most recently boxed label. Suppose this node to be X and let D be its permanent label. Then, in turn, consider each node directly joined to X but not yet permanently boxed. For each such node, Y say, temporarily label it with the lesser of D + (the weight of arc XY) and its existing label (if any).

Step 3: Choose the least of all temporary labels on the network. Make this label permanent by boxing it.

Step 4: Repeat Steps 2 and 3 until the destination node has a permanent label.

Step 5: Go backwards through the network, retracing the path of shortest length from the destination node to the start node.

8) Chinese Postman Algorithm

Step 1: Find all nodes of odd order.

Step 2: For each pair of nodes find the connecting path of minimum weight.

Step 3: Pair up all the odd nodes so that the sum of the weights of the connecting paths from Step 2 is minimised.

Step 4: In the original graph, duplicate the minimum weight paths found in Step 3.

Step 5: Find a trail containing every arc for the new (Eulerian) graph.

9) The Nearest Neighbour Algorithm

Step 1: Choose any starting node.

Step 2: Consider the arcs which join the previously chosen node to not-yet-chosen nodes. From these arcs pick one that has minimum weight. Choose this arc, and the new node on the end of it, to join the cycle.

Step 3: Repeat Step 2 until all nodes have been chosen.

Step 4: Then add the arc that joins the last-chosen node to the first-chosen node.

10) The Lower Bound Algorithm

Step 1: Choose an arbitrary node, say X. Find the total of the two smallest weights of arcs incident at X.

Step 2: Consider the network obtained by ignoring X and all arcs incident to X. Find the total weight of the minimum connector for this network.

Step 3: The sum of the two totals is a lower bound.

11) Tour Improvement Algorithm

Step 1: Let i = 1.

Step 2: If d(V, V) + d(V,V) < d(V, V) + d(V, V), then swap V and V.

Step 3: Replace i by i + 1.

Step 4: If i ≤ n then go back to Step 2.

12) The Simplex Algorithm

Step 1: Formulate the maximising problem (using slack variables as necessary) as a tableau.

Step 2: Ensure that all elements in the last column (except possibly the top one) are non-negative.

Step 3: Select any column (except the last one) whose top element is negative.

Step 4: Call the numbers in the selected column a, a, a, . . . . and the numbers in the last column l, l, l, . . . . In the selected column, choose the positive element a for which is least. This a is called the pivot.

Step 5: Divide the i th row by a.

Step 6: Combine appropriate multiples of the i th row with all the other rows in order to reduce to zero all other elements in the column of the pivot.

Step 7: If all top elements (except possibly the last one) are non-negative then the maximum has been reached. Otherwise return to Step 3.

Step 8: The last column contains the values of the objective function and the non-zero variables.