• Tweet

• Tweet

Shortest route With Graph Coverage

Traversable graphs

A traversable graph is one that can be drawn without taking a pen from the paper and without retracing the same edge. In such a case the graph is said to have an Eulerian trail.

If we try drawing the three graphs shown above we find:

· It is impossible to draw Graph 1 without either taking the pen off the paper or re-tracing an edge

· We can draw Graph 2, but only by starting at either A or D – in each case the path will end at the other vertex of D or A

· Graph 3 can be drawn regardless of the starting position and you will always return to the start vertex.

What is the difference between the three graphs?

In order to establish the differences, we must consider the order of the vertices for each graph. We obtain the following:

When the order of all the vertices is even, the graph is traversable and we can draw it. When there are two odd vertices we can draw the graph but the start and end vertices are different. When there are four odd vertices the graph can’t be drawn without repeating an edge.
To draw the graph with odd vertices, edges need to be repeated. To find such a trail we have to make the order of each vertex even.
In graph 1 there are four vertices of odd order and we need to pair the vertices together by adding an extra edge to make the order of each vertex four. We can join AB and CD, or AC and BD, or AD and BC.
In each case the graph is now traversable.
A minimum spanning tree of a network always has one edge fewer than the number of vertices in the graph (trivially). It may not be unique, but is the shortest length of arcs (edges) required to link every single node (vertex).

Kruskal’s algorithm:

To find a minimum spanning tree for a network with n edges.
Step 1: Choose the unused edge with the lowest value.
Step 2: Add this edge to your tree.
Step 3: If there are n-1 edges in your tree, stop. If not, go to step 1.
NOTE: Ensure you do not create a cycle – if choosing an arc would produce a cycle, don’t choose it.

Prim’s algorithm:

To find a minimum spanning tree for a network with n edges.
Step 1: From a start vertex draw the lowest valued edge to start your tree. (Any vertex can be chosen as the start vertex; however, it will always be given in an exam question.)
Step 2: From any vertex on your tree, add the edge with the lowest value.
Step 3: If there are n-1 edges in your tree, you have finished. If not, go to step 2.
NOTE: Ensure you do not create a cycle – if choosing an arc would produce a cycle, don’t choose it.
Kruskal’s algorithm adds edges regardless of their connectedness to the previously selected edges. Prim’s limits your choice to connected edges.

Shortest path problem (Dijkstra’s algorithm)
Dijkstra’s algorithm

Used for finding the shortest path through a network.
Step 1: Label the start vertex as 0.
Step 2: Box this number (permanent label).
Step 3: Label each vertex that is connected to the start vertex with its distance (temporary label).
Step 4: Box the smallest number.
Step 5: From this vertex, consider the distance to each connected vertex.
Step 6: If a distance is less than the distance already in this vertex, cross out the distance and write in the new distance. If there was no distance at the vertex, write down the new distance.
Step 7: Repeat from step 4 until the destination vertex is boxed.
Note: At step 4, the ‘smallest number’ refers to the smallest available temporary label – this does not need to be directly connected to the latest vertex to be permanently labelled.
Note: in some networks, called directed networks, sometimes edges will be unidirectional (eg, oneway streets). To apply Dijkstra’s algorithm in these cases, only consider edges leading away from the vertex.
If there are multiple start points, then we apply Dijkstra’s algorithm from the end point until we have reached each of the starting points. In this way we can find the shortest route.

Limitations: If we use Dijkstra’s algorithm on a network containing an edge that has a negative value it does not work.

To find the route of the shortest path using Dijkstra’s algorithm:
As well as listing temporary values, we put a letter after each value, which indicates the preceding vertex on the route. We find the route by backtracking through the network from the finishing point.
To find second shortest path, store each path in a priority queue sorted by length of the path.
Maintain a k size priority queue, if kth shortest path is to be calculated.

A* Search Algorithm:

In computer science<http://en.wikipedia.org/wiki/Computer_science>, A* is a computer algorithm<http://en.wikipedia.org/wiki/Computer_algorithm> that is widely used in pathfinding<http://en.wikipedia.org/wiki/Pathfinding> and graph traversal<http://en.wikipedia.org/wiki/Graph_traversal>, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance<http://en.wikipedia.org/wiki/Computer_performance> and accuracy, it enjoys widespread use. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance.

A* uses a best-first search<http://en.wikipedia.org/wiki/Best-first_search> and finds a least-cost path from a given initial node<http://en.wikipedia.org/wiki/Node_(graph_theory)> to one goal node<http://en.wikipedia.org/wiki/Goal_node> (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue<http://en.wikipedia.org/wiki/Priority_queue> of alternate path segments along the way.
It uses a knowledge-plus-heuristic<http://en.wikipedia.org/wiki/Heuristic> cost function of node x (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:
· the past path-cost function, which is the known distance from the starting node to the current node x (usually denoted g(x))
· A future path-cost function, which is an admissible<http://en.wikipedia.org/wiki/Admissible_heuristic> “heuristic estimate” of the distance from x to the goal (usually denoted h(x)).
The h(x) part of the f(x) function must be an admissible heuristic<http://en.wikipedia.org/wiki/Admissible_heuristic>; that is, it must not overestimate the distance to the goal. Thus, for an application like routing<http://en.wikipedia.org/wiki/Routing>, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.
Like breadth-first search<http://en.wikipedia.org/wiki/Breadth-first_search>, A* is complete and will always find a solution if one exists.
Special cases:
Dijkstra’s algorithm<http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>, as another example of a uniform-cost search algorithm, can be viewed as a special case of A* where h(x) = 0 for all x. General depth-first search<http://en.wikipedia.org/wiki/Depth-first_search> can be implemented using the A* by considering that there is a global counter C initialized with a very large value. Every time we process a node we assign C to all of its newly discovered neighbours. After each single assignment, we decrease the counter C by one. Thus the earlier a node is discovered, the higher its h(x) value. It should be noted, however, that both Dijkstra’s algorithm and depth-first search can be implemented more efficiently without including an h(x) value at each node.
A* is admissible<http://en.wikipedia.org/wiki/Admissible_heuristic> and considers<http://en.wikipedia.org/wiki/Consistent_heuristic> fewer nodes than any other admissible search algorithm with the same heuristic. This is because A* uses an “optimistic” estimate of the cost of a path through every node that it considers—optimistic in that the true cost of a path through that node to the goal will be at least as great as the estimate. But, critically, as far as A* “knows”, that optimistic estimate might be achievable.
When A* terminates its search, it has found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A* can safely ignore those nodes. In other words, A* will never overlook the possibility of a lower-cost path and so is admissible.

Chinese postman problem

Dijkstra’s algorithm finds the shortest path between two vertices. The Chinese postman problem is an attempt to find the shortest path which traverses every edge. The obvious application would be a postman who needs to traverse each road in a given area.
To find a minimum Chinese postman route we must walk along each edge at least once and in addition we must also walk along the least pairings of odd vertices on one extra occasion.
An algorithm for finding an optimal Chinese postman route is:
Step 1 List all odd vertices.
Step 2 List all possible pairings of odd vertices.
Step 3 For each pairing find the edges that connect the vertices with the minimum weight.
Step 4 Find the pairings such that the sum of the weights is minimised.
Step 5 On the original graph add the edges that have been found in Step 4.
Step 6 The length of an optimal Chinese postman route is the sum of all the edges added to the total found in Step 4.
Step 7 A route corresponding to this minimum weight can then be easily found.

Step 1 The odd vertices are A and H.
Step 2 There is only one way of pairing these odd vertices, namely AH.
Step 3 The shortest way of joining A to H is using the path AB,
BF, FH, a total length of 160.
Step 4 Draw these edges onto the original network.

Step 5 The length of the optimal Chinese postman route is the sum of all the edges in the original network, which is 840 m, plus the answer found in Step 4, which is 160 m.
Hence the length of the optimal Chinese postman route is 1000 m.
Step 6 One possible route corresponding to this length is ADCGHCABDFBEFHFBA, but many other possible routes of the same minimum length can be found.

How does this problem differ from the problem of the travelling salesman?
The travelling salesman needs to visit every node (or vertex) whereas the Postman needs to travel along each arc (or edge). Therefore it is required that the network is traversable (Eulerian).

Travelling salesman problem

Where the Chinese postman was trying to minimise the distance travelled while traversing every edge, the travelling salesman needs to minimise the distance travelled while visiting every vertex.
A minimum spanning tree links all vertices, but a tour for the travelling salesman must start and finish at the same vertex, meaning that, rather than containing one fewer edges than vertices, it contains the same number.
The optimal tour is defined as a tour of the graph with the shortest path. There is no algorithm for calculating this, and brute force calculations would take prohibitively long, even by computer.
Therefore an upper bound is a useful tool.
Any tour that exists is an upper bound. The best upper bound is the lowest upper bound.
Nearest-neighbour algorithm
Used to find an upper bound for the optimal tour.
Step 1: Choose a start vertex.
Step 2: From your current vertex go to the nearest unvisited vertex.
Step 3: Repeat step 2 until all the vertices have been visited.
Step 4: Return to the start vertex.
Note: By starting at different vertices, different upper bounds can be generated.
Just as an upper bound for the length of an optimal tour can be found, a lower bound can be calculated. Since it only shows that the shortest tour cannot be below this value, it does not necessarily mean that any tour exists with a value as low as this lower bound. Conversely to the upper bound, the best lower bound is the greatest lower bound.
Lower bound algorithm
Used to find a lower bound for the optimal tour.
Step 1: Delete a vertex and all edges connected to the vertex.
Step 2: Find a minimum spanning tree for the remaining network.
Step 3: Add the two shortest edges from the deleted vertex.
Note: You can use either Kruskal’s or Prim’s to find the minimum spanning tree, required in step 2.
An incomplete network is one in which not all vertices are linked by edges. This would result in a contradiction should we apply our upper bound or lower bound algorithms.
If any network is incomplete then before any upper or lower bounds are obtained, the network must be made complete. Ensure that the distances between all pairs of vertices are represented by a single edge of minimum length.