The authors addressed the problem of selecting the cheapest possible route between a source and a destination in a graph in which edges are owned by self agents. The VCG mechanism is the unique efficient mechanism, however the payments made by VCG can be unacceptably high in some graphs. In this paper, they study the VCG overpayment in different types of graphs with unit and uniformly random edge costs. The results suggests that for common real-world networks, the VCG payments will not e too much higher than the true costs.