05-查找最短路径

4.3　查找最短路径

超级高铁的速度太快了，因此若要优化某两个站点间的行进时间，站点间的距离可能就不太重要了，而更重要的是两站之间的跳数（需要经过多少个站点）。每个站点都可能会有中途停留，所以就像乘坐飞机一样，中途停留的站点越少越好。

在图论中，连接两个顶点的一系列边被称为路径（path）。换句话说，路径是从一个顶点到另一个顶点的行进方案。在超级高铁网络中，一系列管道（边）代表从一个城市（顶点）到另一个城市（顶点）的路径。用图解决的最常见问题之一就是查找顶点间的最优路径。

由边依次连接起来的顶点列表可以被非正式地视作路径。这种描述实际上只是换了种说法，就像同一枚硬币的另一面。正如获取边的列表一样，找出边所连接的顶点，留下顶点列表并把边的数据去掉。在以下简短示例中，我们将会找到连接超级高铁网络中两个城市的这种顶点列表。