Weighted graphs
22 March 2010
Introduction
A weighted graph is a graph such that each edge is labelled with a number, called the weight of that edge. There is an example of a weighted graph below (ignore the yellow vertices for the moment).
Weighted graphs are particularly important in optimisation problems. For example, the vertices of the graph above may represent certain towns in England, and the edges may represent roads between the towns, with their separation distances marked. A typical optimisation problem asks how you can travel from one yellow town to the other covering the least possible distance. Try answering this problem; which path is optimal?
Investigation 1: shortest path problem
The optimal path considered in the previous section is called a shortest path. This terminology is suggestive of the hypothetical situation involving roads and towns described above. How, in general, do we find the shortest path between two vertices of a weighted graph? Here is one way: we consider every possible path between the two vertices, and identify which of these paths is shortest. This algorithm is fine for small graphs, but it is slow for large graphs. There are faster algorithms, such as Dijkstra's algorithm. Apply Dijkstra's algorithm to the above weighted graph to construct a shortest path. Try the algorithm out on other graphs.
Investigation 2: Travelling salesman problem
The travelling salesman problem is to find a minimum-weight Hamilton cycle in a weighted complete graph. The vertices of the graph represent towns, and the weighted edges between vertices represent travel times between the towns. The travelling salesman must visit each town (vertex) once only, and return to his starting town, in the minimum amount of time. Consider the travelling salesman problem for the following graph.
For the above graph, let us begin with the Hamilton cycle that moves round the edge of the graph along the vertices A,B,C,D,E,F,A. This cycle has total weight 56+21+36+51+13+60=237. We can modify this cycle step by step to obtain a cycle with less weight. For example, reverse the string "D,E,F" to obtain a new cycle A,B,C,F,E,D,A with weight 211. Next, reverse the string "B,C" to obtain a new cycle A,C,B,F,E,D,A with weight 192. Each time we reverse a string we replace two edges of the cycle. Is A,C,B,F,E,D,A the optimal cycle? In general, this algorithm will not give the optimal cycle.