这类背景一般是类似:已知各城市之间距离,请给出从城市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