Mikeem's Favorite Links on algorithm from Diigo

Dijkstra's Algorithm

Mon, 17 Dec 2007 01:46:51 -0000

Posted by: mikeem

THE CHINESE POSTMAN PROBLEM - ALGORITHM FOR NETWORKS INVOLVING ODD VERTICES WITH DISCUSSION

Sun, 16 Dec 2007 23:08:21 -0000

Highlights and Sticky Notes:

Note also that by considering this algorithm, it is relatively easy to see how to modify Fleury’s algorithm for finding an Euler circuit in a graph with two odd vertices if it is necessary to return to the starting vertex. We would simply construct an extra path between the two vertices, and this path would represent the extra distance that we would need to travel in order to be able to go back to the start. Clearly in this case the solution would no longer be a semi-Eulerian circuit (nor would it be an Eulerian circuit, as we are effectively traversing a part of the network twice to accommodate the desire to return to the starting point).

We can see from the way that odd vertices are paired in the algorithm that the minimum circuit for any network will always have a length of less than twice the sum of all the weightings on the graph. This is because each edge in the network must be traversed once, by definition. Any extra parts added onto the route, i.e. repeated edges, will minimise the total distance from considering all possible pairings of odd vertices. As the number of odd vertices must be less than or equal to the number of vertices in total, then the optimal way in which this is done means that the extra length added must be less than the sum of the lengths of the entire original network. Thus, a relatively good route will always exist given even the most difficult network (one with only odd vertices).

If the graph has more than two vertices of odd degree, we will have to retrace some of the edges in order to traverse all edges at least once, which makes sense. This assumes that we wish to finish up at the same vertex that we started out from.

By applying this algorithm, we are effectively converting the vertices of odd degree to even degree by adding additional edges. The process of eliminating odd vertices by adding additional edges is called “Eulerising” the graph. Once the additional edges have been added in, we can simply apply Fleury’s algorithm to the modified network to obtain an optimal solution.

3) For each set of pairings, for each pairing, find the shortest route you need to travel to get from one vertex in the pairing to the other. Hence, add up the total distance you need to travel for each set of possible pairings.

4) Choose the pairing with the minimum total distance and repeat these edges in the network, i.e. makes the associated vertices have an even degree. Note: there may be many different routes that can be constructed, all of which take the same minimum distance.

2) In order to make the network Eulerian, find possible all possible sets of pairings of odd vertices in order to make them of even degree so that no odd vertices are left in the network.

1) List all odd vertices in the network. There will be an even number of these.

It may well be the case that the network we are dealing with does indeed contain odd vertices, and where we wish to return to our starting vertex. In this circumstance, we require a different algorithm to obtain a solution.

Tags: algorithm exam maths postman

Posted by: mikeem

THE CHINESE POSTMAN PROBLEM - MODIFICATION OF FLEURY'S ALGORITHM

Sun, 16 Dec 2007 23:00:59 -0000

Highlights and Sticky Notes:

This is what we would have expected from our earlier analysis, and what the algorithm is designed to do, so we have applied it correctly. The semi-Eulerian circuit achieved is shown in green on the diagram below.

We must start at one of the odd vertices, let us say D.

• From here, we can select to go to any of the vertices E or G. Let us select G, as shown in the diagram.

• Then we will traverse edge GC.

• Next, we are forced to select CB, even though it is a bridge for the remaining edges at this stage.

• From here, we will go to G, and then back to D (allowed as GD is not a bridge for remaining edges).

• Then we will traverse the edge DE (although we know we must finish at vertex E, this is allowed, as DE is not a bridge for remaining arcs, and it is clear from the diagram that we are able to return later as there are three edges incident upon E).

• Continuing to apply the algorithm, we get EG, GF, FA, AB.

• At B, we have to select edge BF, because it is the only remaining edge leading out from B, although it is a bridge.

• Finally, we take edge FE to finish at E, the other odd vertex.

Use Fleury's Algorithm just as stated above EXCEPT always start at one of the odd vertices.

The path produced by this modification of Fleury's algorithm is always a semi-Eulerian cycle for the reasons discussed previously.

Tags: algorithm exam maths postman

Posted by: mikeem

THE CHINESE POSTMAN PROBLEM - FLEURY'S ALGORITHM

Sun, 16 Dec 2007 22:44:51 -0000

Highlights and Sticky Notes:

At the next stage, it would appear that I have three choices of arc to travel along. However, if we consider only the remaining edges that are not yet included in the solution, we can see that FA is now a bridge, and so we must not select this choice (we can now see why this rule works now; we would be “trapped” at A if we selected the edge FA, having to include the same arc twice). We will choose FE arbitrarily from the remaining options.

• We will now continue our circuit without complication as there are no bridges for remaining arcs, using edges ED, DG, GD.

• Note now that we are at D that we only have one arc choice, DE. This is a bridge for remaining edges, and so normally would not be allowed. However, as it is the only option, we must select it, as the algorithm states. This will happen many times throughout the remainder of the application of the algorithm. Each time, we are leaving a vertex for the final time.

• Finishing off the algorithm with the bridge constraint gives the inclusion of edges EG, GC, CB, BG, GF, FA.

• Thus, we have an Euler circuit through our network as required. This has been marked on the original network diagram shown below in green.

This algorithm can be applied to any network only containing vertices of an even degree.

Following the algorithm, then:

• I will arbitrarily choose A to be my starting vertex.

• From here, I have a choice of which edge to travel along, as neither the edges AB nor AF are bridges. I will select AB.

• Next, I will choose to travel to F via the edge BF, which is again valid under the bridge constraint.

Let us see an example of this algorithm at work. Here, I have invented a network that has seven vertices, all of which are of an even order. It therefore satisfies the conditions for Fleury's algorithm to work.

Here, the second point is effectively saying that you should not go back to the starting vertex until you have to, i.e. right at the end of the construction of the path, as required.

The algorithm is as follows:

• Pick any vertex as a starting point.

• Marking your path as you move from vertex to vertex, travel along any edges you wish, except do not travel along an edge that is a bridge for the graph formed by the edges that have yet to be traversed unless you have to .

• Continue until you return to your starting point.

Tags: algorithm exam maths postman

Posted by: mikeem