这类背景一般是类似：已知各城市之间距离，请给出从城市A到城市B的最短行车方案 or 各城市距离一致，给出需要最少中转方案。
也就是，固定起始点的情况下，求最短路。
这个问题用简单的搜索就能轻松解决。（本部分内容不涉及图论算法，可跳过）
假设用邻接矩阵存图，就比如下面这个例子：
深度优先搜索（dfs）的做法：
void dfs(int cur, int dis) //cur-当前所在城市编号，dis-当前已走过的路径{if(dis > min) return; //若当前路径已比之前找到的最短路大，没必要继续尝试（一个小优化，可以不写）if(cur == n) //当前已到达目的城市，更新min{if(dis < min) min = dis;return;}for(int i = 1; i 5 距离变成9了。事实上，每个顶点都有可能使另外两个顶点间的路程变短。这种通过中转变短的操作叫做松弛。当任意两点间不允许经过第三个点时，这些城市之间的最短路程就是初始路程：
假如现在允许经过1号顶点的中转，求任意两点间的最短路，这时候就可以遍历每一对顶点，试试看通过1号能不能缩短他们的距离。
for(int i = 1; i 3这条边能否让1号到3号的路程变短，也即比较dis[3]和dis[2]+e[2][3]的大小。发现是可以的，于是dis[3]从12变为新的更短路10。同理，通过2->4也条边也更新下dis[4]。松弛完毕后dis数组变为：
接下来，继续在剩下的 3 4 5 6 结点中选一个离1号最近的结点。发现当前是4号离1号最近，于是dis[4]确定了下来，然后继续对4的所有出边看看能不能做松弛。
balabala，这样一直做下去直到已经没有“剩下的”结点，算法结束。
这就是Dijkstra算法，整个算法的基本步骤是：
所有结点分为两部分：已确定最短路的结点集合P、未知最短路的结点集合Q。最开始，P中只有源点这一个结点。（可用一个book数组来维护是否在P中）在Q中选取一个离源点最近的结点u（dis[u]最小）加入集合P。然后考察u的所有出边，做松弛操作。重复第二步，直到集合Q为空。最终dis数组的值就是源点到所有顶点的最短路。代码：
for(int i = 1; i 5这条边的时候，虽然松弛成功，dis[5]从10更新为9了，但5号顶点已经在队列中，所以5号不能再次入队。处理完2号之后就长这样：
接着一直持续下去，直到队列为空，算法结束。
代码：
for(int i = 1; i