SECTION 2.2 Elementary Graph Theory 131
- Use Prim’s algorithm to find a minimal spanning tree in the graph
below: - Use the methods of Exercise 3 on page 129 to find upper and lower
bounds on the weight of a Hamiltonian cycle in the above graph.
Weighted directed graphs; Dijkstra’s algorithm
In many applications of graph theory, one notices that the cost of mov-
ing from vertexv 1 to the vertexv 2 might be different from the cost of
moving fromv 2 to the vertexv 1.^34 Such a graph is called aweighted
directed graph. Of interest in this setting is to find the minimal
weight (cost) in getting from an initial vertex—call itv 0 —to some other
vertexv.^35
Below is depicted a weighted directed graph:(^34) For example the price of a airline ticket from Shanghai to Beijing is typically (slightly) less than
the price of a ticket from Beijing to Shanghai. 35
This is sometimes called theminimal connector problem.