看完就懂了！一篇搞定图论最短路径问题
最最原始的问题——两点间的最短路
这类背景一般是类似：已知各城市之间距离，请给出从城市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 <= n; i++) //对1~n号城市依次尝试 { if(e[cur][i] != INF && book[i] == 0) //若cur与i可达，且i没有在已走过的路径中 { book[i] = 1; //标记i为已在路径中 dfs(i, dis+e[cur][i]); //继续搜索 book[i] = 0; //对从i出发的路径探索完毕，取消标记 } } }顺带插播一下如何理解DFS算法，它的关键思想仅在于解决当下该如何做。至于“下一步如何做”则与“当下该如何做”是一样的，把参数改为进入下一步的值再调用一下dfs()即可。
而在写dfs函数的时候就只要解决当在第step的时候你该怎么办，通常就是把每一种可能都去尝试一遍。当前这一步解决后便进入下一步dfs(step+1)，剩下的事情就不用管它了。
基本模型：
void dfs(int step) { 判断边界 尝试每一种可能 for(int i = 1; i <= n; i++) { 继续下一步 dfs(step+1) } }但对于所有边权相同的情况，用广度优先搜索会更快更方便。
比如上面提到的最少中转方案问题，问从城市1到城市4需要经过的最少中转城市个数。
用广搜的做法：
int bfs() { queue<pair<int,int>> que; //pair记录城市编号和dis，也可以用结构体 que.push({1,0}); //把起始点加入队列 book[1] = 1; //标记为已在路径中 while(!que.empty()) { int cur = que.front(); que.pop(); for(int i = 1; i <= n; i++) { if(e[cur][i] != MAX && book[i] == 0) //若从cur到i可达且i不在队列中，i入队 { que.push({i, cur.second+1}); book[i] = 1; if(i == n) return cur.second; //如果已扩展出目标结点了，返回中转城市数答案 } } } }以上都是开胃，下面才是真的重点来了~
膨胀——任意两点间的最短路
已经知道了求解固定两点间的最短路，那要怎么求任意两点间的最短路呢？显然，可以进行n^2次的dfs或bfs轻松搞定（被打）。
观察会发现，如果要让两点 i , j 间的路程变短，只能通过第三个点 k 的中转。比如上面第一张图，从 1->5 距离为10，但 1->2->5 距离变成9了。事实上，每个顶点都有可能使另外两个顶点间的路程变短。这种通过中转变短的操作叫做松弛。
当任意两点间不允许经过第三个点时，这些城市之间的最短路程就是初始路程：
假如现在允许经过1号顶点的中转，求任意两点间的最短路，这时候就可以遍历每一对顶点，试试看通过1号能不能缩短他们的距离。
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(e[i][j] > e[i][1]+e[1][j]) e[i][j] = e[i][1]+e[1][j]; }更新后果然有好几条变短了：
扩展一下，先允许1号顶点作为中转给所有两两松弛一波，再允许2号、3号...n号都做一遍，就能得到最终任意两点间的最短路了。
这就是Floyd算法，虽然时间复杂度是令人发怵的O(n^3)，但核心代码只有五行，实现起来非常容易。
for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(e[i][j] > e[i][k]+e[k][j]) e[i][j] = e[i][k]+e[k][j];最常见的问题——单源最短路
传说中如雷贯耳的“单源最短路”应该是做题中最常见到的问题了。也即，指定源点，求它到其余各个结点的最短路。
比如给出这张图，假设把1号结点作为源点。