10-在加权图中查找最短路径

4.5　在加权图中查找最短路径

随着超级高铁网络的开建，建造商不大可能有雄心一次就实现整个国家的连通。他们可能希望最大限度地降低在主要城市之间铺设轨道的成本。将超级高铁网络延伸至某个城市的成本显然取决于从哪里开始修建。

计算从某个起点城市到任一城市的成本是一种“单源最短路径”（single-source shortest path）问题。此问题可以表述为：“在加权图中，从某个顶点到其他每个顶点的最短路径（以边的总权重计）是什么？”