标题前面打*号的为多数考纲范围外的，可以选择性查看
🔗链接：严书代码大全
🔗链接：c/c++语言算法技巧汇总大复习1
🔗链接：c/c++语言算法技巧汇总大复习2
目录
- Dp动态规划
- 入门练习 青蛙跳台阶
- 练习：给定一个整数数组 nums ，找到一个连续子数组（子数组最少包含一个元素），返回其最大和。
- dfs or 回溯法
- 练习1 数独游戏
- 练习2:排列数字
- *template模版
- *单位分数之和
- 埃及分数（贪心法）
- 进阶
- *vector or list
- 图进阶
- *图的割点
- *图的割边
- *二分图
- *贝尔曼福特算法（Bellman-Ford）-单源
- *贝尔曼福特算法的队列优化
Dp动态规划
入门练习 青蛙跳台阶
台阶总共n级，青蛙一次能跳1～n级台阶，求跳到n级台阶有几种跳法g(n)？
明确递推关系，已知g(1)=1,g(2)=2，g(3)=g(1)+g(2)+直接跳三个台阶（这种设为g(0)，g(0)=1）
也可以根据递推关系得到g(n)=2*g(n-1)(n>=3)
int count(int n){
if(n==1)return 1;
else if(n==2)return 2;
else if(n>2){
int c=0;
for(int i=0;i<n;i++)
c+=count(i);
return c;
}
}
练习：给定一个整数数组 nums ，找到一个连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
#include <iostream>
#include<stdio.h>
using namespace std;
int main(){
int a[1000]={0};
int t;
int len=0;
while(scanf("%d", &t) != EOF) a[len++]=t;
int max=0;
int sum=0;
for(int i=0;i<len;i++){
sum=0;
for(int j=i;j<len;j++)
{
sum+=a[j];
cout<<"+"<<a[j]<<endl;
if(sum>max)max=sum;
}
}
cout<<max;
return 0;
}
dfs or 回溯法
DFS 英文名，Depth First Search，中文名 深度优先搜索，是图的一种搜索算法，每一个可能的分支路径深入到不能再深入为止，且每个节点只能访问一次。
深度优先搜索算法跟图结构紧密相关，任何涉及深度度优先搜索的问题，都伴随着图。深度度优先搜索的能够在图结构里搜索到通往特定终点的一条或者多条特定路径。
回溯算法是系统地搜索问题的解的方法。某个问题的所有可能解的称为问题的解空间，若解空间是有限的，则可将解空间映射成树结构。任何解空间可以映射成树结构的问题，都可以使用回溯法。回溯法是能够在树结构里搜索到通往特定终点的一条或者多条特定路径。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。
值得注意，回溯法以深度优先搜索的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
不能简单的说：回溯算法 = 深度优先搜索 + 剪枝函数。因为并不是所有图都是树。深度优先搜索适用于所有图。而回溯算法只适用于树结构。
练习1 数独游戏
玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。
数独的答案都是唯一的，所以，多个解也称为无解。
本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。
本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。
格式要求，输入9行，每行9个字符，0代表未知，其它数字为已知。
输出9行，每行9个数字表示数独的解。
例如：
输入（即图中题目）：
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
程序应该输出：
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764
再例如，输入：
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400
程序应该输出：
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms
#include <stdio.h>
int a[9][9];
int place(int x, int y) //二者分别是数组对应的行地址和列地址，取值为0-8
{
int up, down, left, right;
int i,j;
//算出同色格范围
up=x/3*3;
down=up+3;
left=y/3*3;
right=left+3;
//以下分三种情况判断是否在x,y对应的位置放这个数，如果不可以放，返回0，如果可以放，返回1，会进一步迭代
for(i=0;i<9;i++){
if(a[x][y]==a[i][y] && i!=x && a[i][y]!=0)//行检查
return 0;
}
for(i=0;i<9;i++){
if (a[x][y]==a[x][i] && i!=y && a[x][i]!=0)//列检查
return 0;
}
for(i=up;i<down;i++)//同色9宫格的情况
{
for(j=left;j<right;j++)
if(i!=x || j!=y)//不是自己即可
{
if(a[i][j]==a[x][y] && a[i][j]!=0)
return 0;
}
}
return 1;
}
void backtrack(int t)//第几个格子
{
int i,j;
int x,y;
if(t==81)
{
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d",a[i][j]);
putchar('\n');
}
}
else
{
x=t/9;
y=t%9; //将这个转换为相应的数组行坐标和列坐标
if(a[x][y]!=0)
{
backtrack(t+1);
}
else
{
for(i=1;i<10;i++)
{
a[x][y]=i;
if(place(x,y)==1)
backtrack(t+1);//探索在此基础上后续的解空间
a[x][y]=0;//还要撤回 尝试该点的其余可能
}
}
}
}
int main()
{
char str[9][9];
int i,j;
for(i=0;i<9;i++)
gets(str[i]);
for(i=0;i<9;i++)
for(j=0;j<9;j++)
a[i][j]=str[i][j]-'0';
backtrack(0);
return 0;
}
练习2:排列数字
今有7对数字：两个1，两个2，两个3，…两个7，把它们排成一行。
要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列：17126425374635当然，如果把它倒过来，也是符合要求的。请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stdlib.h>
#include<algorithm>
#include<cmath>
using namespace std;
int arr[16]={0};
int dfs(int n)
{
if(n > 6) return 1;//因为7距离已经确定，所以最大距离就是6
if(n == 4) n++;//因为当n=4，两者距离就是4，4的位置已经确定，所以跳过
int i=3;
for(;i <=14 ;i++)
{
if(i == 7 || i == 9) continue;//下标7,9位置值已经定了
if(i+n+1 <=14 && arr[i]==0 &&arr[i+n+1]==0)//保证两个位置都没有数据
{
arr[i] = arr[i+n+1] = n;
if(dfs(n+1))//继续在此基础上探索下一个即n+1距离解空间
return 1;
arr[i] = arr[i+n+1] = 0;//恢复上一次dfs状态，探索n的新可能
}
}
return 0;
}
int main()
{
arr[1] = 7,arr[2] = 4;//因为题目上已经给出两个开头，可以推出后面两个
arr[9] = 7,arr[7] = 4;
dfs(1);//先确定两个1
for(int i = 1;i < 16;i++ )
{
cout <<arr[i];
}
cout <<"\n";
return 0;
}
*template模版
在没有泛型编程时，只能使用函数重载逐个写，每次都要摘过来一段代码。
重载的函数仅仅是参数列表中的类型不同，代码复用率比较低，只要有新类型出现时，就需要用户自己增加对应的函数代码的可维护性比较低，一个出错可能所有的重载均出错。
泛型编程：编写与类型无关的通用代码，是代码复用的一种手段。模板是泛型编程的基础模板，分为函数模板和类模板。函数模板只是一个蓝图，在实例化时，根据推导的参数的类型来生成特定的版本。
template<typename T1, typename T2…, typename Tn>typename是用来定义模板参数的关键字，也可以使用class(切记：不能使用struct代替class)
*单位分数之和
埃及分数（贪心法）
埃及分数：分子是1的分数，也叫单位分数。古代埃及人在进行分数运算时，只使用分子是1的分数。如：8/11=1/2+1/5+1/55+1/110。
真分数：分子比分母小的分数，叫做真分数。真分数的分数值小于1。如1/2，3/5，8/9等。输入一个真分数，请将该分数分解为埃及分数。一个真分数的埃及分数表示并不唯一。
贪心法，则是要让一个真分数被埃及分数表示的个数最少，每次选择不大于真分数的最大埃及分数。
假设需要求解真分数 A / B (A 与 B 不可约)，
那么假设 B = A * C + D， B / A = C + D / A < C + 1，A / B > 1 / (C + 1);
按照贪心的思想，1 / (C + 1) 为 A / B 分解中最大的那个分子为 1 的真分数。
假设 E = (C + 1)，那么相减以后得到 A / B - 1 / E = (A * E - B ) / B * E，
那么得到新的A = A * E - B，B = B * E,然后对新的 A / B 进行约分，保证下一轮的 A 与 B 不可约。
如此循环，当 A = 1 是表明结束循环，得到答案。
#include<bits/stdc++.h>
using namespace std;
void EgyptFraction(int A,int B){
cout << A << '/' << B << '=';
int E,R;
while(A != 1){
E = B / A + 1; //B / A = C.
cout << "1/" << E << '+';
A = A * E - B;
B = B * E;
R = __gcd(A,B);
if(R > 1){
A /= R;
B /= R;
}
}
cout << "1/" << B;//A 是 1 了直接输出 1 / B 即可，此时结束分解。
}
int main(){
int A,B;
cin >> A >> B;
EgyptFraction(A,B);
return 0;
}
进阶
形如：1/a 的分数称为单位分数。
可以把1分解为若干个互不相同的单位分数之和。
例如：
1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
等等，类似这样的分解无穷无尽。
我们增加一个约束条件：最大的分母必须不超过30
请你求出分解为n项时的所有不同分解法。
数据格式要求：
输入一个整数n，表示要分解为n项（n<12）
输出分解后的单位分数项，中间用一个空格分开。
每种分解法占用一行，行间的顺序按照分母从小到大排序。
例如，
输入：
4
程序应该输出：
1/2 1/3 1/8 1/24
1/2 1/3 1/9 1/18
1/2 1/3 1/10 1/15
1/2 1/4 1/5 1/20
1/2 1/4 1/6 1/12
再例如，
输入：
5
程序应该输出：
1/2 1/3 1/12 1/21 1/28
1/2 1/4 1/6 1/21 1/28
1/2 1/4 1/7 1/14 1/28
1/2 1/4 1/8 1/12 1/24
1/2 1/4 1/9 1/12 1/18
1/2 1/4 1/10 1/12 1/15
1/2 1/5 1/6 1/12 1/20
1/3 1/4 1/5 1/6 1/20
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms
先研究一下数学原理
1=30/30
这个分母就是30，分子也是30，将分子的30做分解就可以了。列出1-29之内相加等于30的各种可能，然后将这些数和分母约分就可以了
比如:30=2+3+25
则1=(2+3+25)/30
1=1/15+1/10+5/6
加了限制项n 时，就更加好办了，就是求n个数相加等于30
等式可以认为是(a1+a2+...am)/K，很好理解，a1,...am必然是K的所有约数的和的组合。因此最后题目就是转化为求一个数K的所有约数，题目K最大才30，之后求出所有约数中,n个数的和等于K的组合。
比如：K=30，30=2*3*5，根据“约数个数定理”，约数有8个，除去自己本身和1就剩6个，为2,3,5,6,10,15,
如果你输入n=4，那么就是求这6个约数中，哪4个相加正好等于30的所有组合，根据组合原理，C(7,4)才210种组合，因此循环不会很久。
题目没规定K值，因此，需要K从1到30循环，对每一次循环的K，找出所有所有约数，并对所有约数个数不小于n的情况，循环找出所有n个约数等于K的组合。
拆分步骤：
1、约数个数定理
2、求一个数的所有约数
3、从N个数中任选M个数相加的和等于K（循环应该就能解决）
第二种方法：dfs
dfs需要具备的基本元素：1.初值 2.什么时候跳出 3.迭代方式（搜索空间要包括全部可探索空间）
#include <iostream>
#include <cmath>
using namespace std;
int n,ans[15];
const double eps=1e-9;
void dfs(double sum,int cnt,double now)//sum 分数加和，cnt当前几个分数相加，now最大分母的值
{
if(cnt==n){
if(abs(sum-1)<eps){
for(int i=0;i<n;i++)
cout<<1<<'/'<<ans[i]<<' ';//ans数组存储依次相加分数的分母
cout<<endl;
}
return ;
}
if(sum>=1||cnt>n||now>30)
return ;
dfs(sum,cnt,now+1);
ans[cnt]=now;
dfs(sum+1/now,cnt+1,now+1);
return ;
}
int main()
{
cin>>n;
dfs(0,0,1);
return 0;
}
*vector or list
一、vector结构上的优点：
由于底层结构是一块连续的空间，所以可以支持下标’‘[]’'随机访问的形式。
cpu高速缓存命中率高。
尾插尾删除效率高，相比list
二、vector结构上的缺点：
越远离头部位置（除了尾部之外）的插入、删除效率低。
扩容有消耗，存在一定的空间的浪费，无论是手动扩还是自动扩，一般来说扩二倍比较合适。
三、list结构上的优点：
任何位置的插入删除的效率比较高，相比list。
按需申请释放节点，空间利用率高，不存在扩容操作。
四、list结构上的缺点：
不支持下标随机访问。
cpu高速缓存命中率低。
五、使用场景：
若存在大量的中间插入删除，考虑用list；否则用vector。list与vector互补配合。
图进阶
*图的割点
割点：无向连通图中删除某个顶点后图不再连通。
如何求割点？
- 最简单的方法是依次删除每一个顶点，看dfs/bfs检查图是否连通，时间复杂度是o(n(n+m))
- 先用dfs/bfs进行遍历，得到图的一个生成树，不一定是最小生成树，按照遍历顺序依次编号（记为时间戳）。在遍历时必有一个为割点，假如dfs访问到了k点，图被k点分成两部分，一个是访问过的点，另一部分是未被访问的点，如果k是割点，则剩下未被访问的点至少会有一个点在不经过k点的情况下不能再回到已访问的点，则被k分为多个不连通的子图。
这个用程序怎么判定？从生成树角度来看如何检测顶点v在不经过父节点u（看时间戳）情况下还能回到祖先？可以重新对顶点v进行一次dfs，但不允许经过u。需要数组low记录每个顶点在不经过父节点时能够访问到的最小时间戳。如果low[v]>=num[u]则u为割点。
#include<stdio.h>
int n,m,e[9][9],root;
int num[9],low[9],flag[9],index;//Index用来进行时间戳的递增
//求两个数中较小的一个数的函数
int min(int a,int b)
{
return a < b ? a : b ;
}
//割点算法的核心
void dfs(int cur, int father ) //需要传入两个参数，当前顶点的编号和父顶点的编号
{
int child=0,i,j;//child用来记录在生成树中当前顶点cur的儿子个数
index++;//时间戳加1
num[cur]=index;//当前顶点cur的时间戳
low[cur]=index;//当前顶点cur能够访问到最早顶点的时间戳，刚开始当然是自己啦
for(i=1;i<=n;i++)//枚举与当前顶点cur有相连边的顶点i
{
if(e[cur][i]==1)
{
if(num[i]==0)//如果顶点i的时间戳不为0，说明顶点i还没有被访问过
{
child++;
dfs(i,cur);//继续向下深度优先遍历
//更新当前顶点cur能否访问最早顶点的时间戳
low[cur]=min(low[cur],low[i]);
//如果当前顶点不是根结点并且满足low[i]>=num[cur],则当前顶点被称为割点
if(cur!=root &&low[i]>=num[cur])
flag[cur]=1;
//如果当前顶点是跟结点，在生成树中根结点必须要有2个儿子，那么这个根结点才是割点
if(cur==root &&child==2)
flag[cur]=1;
}
else if(i!=father)
//否则如果顶点i曾经被访问过，那么这个顶点不是当前顶点cur的父亲，则需要更新当前结点cur能否访问到最早顶点的时间戳
{
low[cur]=min(low[cur],num[i]);
}
}
}
}
int main()
{
int i,j,x,y;
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=0;
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
e[x][y]=1;
e[y][x]=1;
}
root=1;
dfs(1,root);//从1号顶点开始进行深度优先遍历
for(i=1;i<=n;i++)
{
if(flag[i]==1)
printf("%d ",i);
}
getchar();
getchar();
return 0;
}
*图的割边
割边：无向连通图中删除某条边后图不再连通。
如何求割边？修改割点算法中的一个符号即可。即low[v]>=num[u]改成low[v]>num[u]
low[v]>=num[u]表示的是不可能不经过父亲节点u到祖先（包括父亲），low[v]==num[u]表示还可以回到父亲，low[v]>num[u]表示（没有另外一条路）返回到父亲；则u-v为割边。符合割边的定义。
割点和割边算法中都是采用邻接矩阵来存储图,时间复杂度是o(n+m)，若改成邻接表的话时间复杂度为o(n^2)，
用依次删除再dfs/bfs检查是否连通 时间复杂度是o(m(n+m))。
//图的割边
#include<stdio.h>
int n,m,e[9][9],root;
int num[9],low[9],flag[9],index;//Index用来进行时间戳的递增
//求两个数中较小的一个数的函数
int min(int a,int b)
{
return a < b ? a : b ;
}
//割点算法的核心
void dfs(int cur, int father ) //需要传入两个参数，当前顶点的编号和父顶点的编号
{
int i,j;
index++;//时间戳加1
num[cur]=index;//当前顶点cur的时间戳
low[cur]=index;//当前顶点cur能够访问到最早顶点的时间戳，刚开始当然是自己啦
for(i=1;i<=n;i++)//枚举与当前顶点cur有相连边的顶点i
{
if(e[cur][i]==1)
{
if(num[i]==0)//如果顶点i的时间戳不为0，说明顶点i还没有被访问过
{
dfs(i,cur);//继续向下深度优先遍历
//更新当前顶点cur能否访问最早顶点的时间戳
low[cur]=min(low[cur],low[i]);
//如果当前顶点不是根结点并且满足low[i]>=num[cur],则当前顶点被称为割点
if(low[i]>num[cur])
printf("%d-%d\n",cur,i);
}
else if(i!=father)
//否则如果顶点i曾经被访问过，那么这个顶点不是当前顶点cur的父亲，则需要更新当前结点cur能否访问到最早顶点的时间戳
{
low[cur]=min(low[cur],num[i]);
}
}
}
}
int main()
{
int i,j,x,y;
scanf("%d %d",&n,&m);//n个顶点，m条边
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=0;
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);//表示两个顶点之间有边
e[x][y]=1;
e[y][x]=1;
}
root=1;
dfs(1,root);//从1号顶点开始进行深度优先遍历
getchar();
getchar();
return 0;
}
*二分图
二分图：一个图的所有顶点可被分为x和y两个集合，所有边的两个顶点恰好一个属于x集合，一个属于y集合，即每个集合内的顶点没有边相连。
如何求出二分图的最大分配（匹配数最多的）？
暴力就是找出全部匹配，然后选出匹配数最多的。
找到一条增广路（一条路径起点终点都是未配对的点），配对数+1
如何确定是最大匹配？如果在当前匹配情况下再找不到增广路，则是最大匹配。
- 首先从任意一个未被匹配的点u开始，从点u的边中任意选一条边开始配对。若点v还没有配对，则配对成功，此时便是一条增广路；再看看是否发生连锁反应，如果尝试成功找到增广路，需要更新原来的配对关系（用match数组记录）；如u和v配对则记match[v]=u，配对数+1；配对过程可用dfs/bfs实现。
- 如果刚才选的边匹配失败，要从点u的边中再重新选一条边进行尝试直到u配对成功或者尝试点u所有的边为止。
- 接下来继续对剩下没有被配对的点一一配对，直到所有点都尝试完毕，找不到新的增广路为止。
- 输出配对数。
如果二分图有n个点则最多n/2条增广路径。如过图中共m条边，那么每找到一条增广路径最多把所有边遍历一遍，所花时间是m，算法总时间复杂度为o(mn)
如何判断一个图是否是二分图？将任意一个顶点着红色，其相邻的点着蓝色，直到所有顶点都能够着色，且相邻顶点颜色不同则为二分图。
#include<stdio.h>
int e[101][101];
int match[101];
int book[101];
int n,m;
int dfs(int u)
{
int i;
for(i=1;i<=n;i++)
{
if(book[i]==0 &&e[u][i]==1);
{
book[i]=1;//标记点i已经被访问过
//如果点i还没有被匹配或者找到了新的配对
if(match[i]==0 || dfs(match[i]))
{
//更新配对关系
match[i]=u;
match[u]=i;
return 1;
}
}
}
return 0;
}
int main(){
int i,j,t1,t2,sum=0;
//读入n和m,n表示顶点数目，m表示边的数目
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++) //读入边
{
scanf("%d%d",&t1,&t2);
e[t1][t2]=1;
e[t2][t1]=1;
}
for(i=1;i<=n;i++) match[i]=0;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++) book[j]=0;//清空上次搜索的时候的标记
if(dfs(i)) sum++;//寻找增广路，如果找到，配对数加1
}
printf("%d",sum);
getchar();
getchar();
return 0;
}
*贝尔曼福特算法（Bellman-Ford）-单源
思想和代码上堪称完美的最短路算法，有兴趣的可以了解下。因为它可以完美解决带有负权边的图，代码也非常简单只有4行。
用于计算一个节点到其他节点的最短路径。（Dijkstra算法也是）
基本原理：逐遍的对图中每一个边去迭代计算起始点到其余各点的最短路径，执行N-1遍，最终得到起始点到其余各点的最短路径。（N为连通图结点数）
负权回路：绕一圈绕回来发现到自己的距离从0变成了负数，到各结点的距离无限制的降低，停不下来。
与迪杰斯特拉算法的区别：
1. 迪杰斯特拉算法是借助贪心思想，每次选取一个未处理的最近的结点，去对与他相连接的边进行松弛操作；贝尔曼福特算法是直接对所有边进行N-1遍松弛操作。
2. 迪杰斯特拉算法要求边的权值不能是负数；贝尔曼福特算法边的权值可以为负数，并可检测负权回路。
第一轮松弛得到的是1号顶点只能经过一条边到达其余各点的最短路径长度
第二轮松弛得到的是1号顶点只能经过两条边到达其余各点的最短路径长度
…
执行n-1轮 因为含有n个顶点的图中任何两点之间的最短路径最多包含n-1条边，所以n-1轮松弛就够了。也就是说有可能不到n-1轮松弛就能得到该点的最短路径。（这里是否能够再优化一下呢？看下文）
通过这里也可以发现该算法的另一个作用是检测图是否有负权回路。如果在n-1轮后仍存在if(dis[v[i]]>dis[u[i]]+w[i]) dis[v[i]]=dis[u[i]]+w[i];则可以证明必存在负权回路。
最短路径不可能包含回路，即不包含正权回路也不包含负权回路。
- 如果最短路径包含正权回路，则去掉这个回路一定能得到更短的路径。
- 如果包含负权回路，则肯定没有最短路径，因为每走一次负权路径都能得到更短的。
时间复杂度是o(nm)我们可以进一步优化，当未达到n-1轮松弛前就计算出最短路，故可以根据check标记dis在本轮松弛是否发生变化，若未变化则提前跳出循环。
当然还有另外一种优化思路，见下一节。
//核心代码
for(k=1;k<=n-1;k++)//枚举n-1个顶点
for(i=1;i<=m;i++)//枚举每条边
if(dis[v[i]]>dis[u[i]]+w[i])//u,v,w定义同dijkstra那节
//u[i]起点的最短路径+其相连的边权值是否比现在v[i]终点最短路径小
dis[v[i]]=dis[u[i]]+w[i];
//优化：提前跳出
for(k=1;k<=n-1;k++)//枚举n-1个顶点
{ check=0;
for(i=1;i<=m;i++)//枚举每条边
{ if(dis[v[i]]>dis[u[i]]+w[i])//u,v,w定义同dijkstra那节
//u[i]起点的最短路径+其相连的边权值是否比现在v[i]终点最短路径小
{ dis[v[i]]=dis[u[i]]+w[i];
check=1;
}
}
if(check==0)break;
}
//检测负权回路 n-1轮代码之后再放置一个
flag=0;
for(i=1;i<=m;i++)//枚举每条边
if(dis[v[i]]>dis[u[i]]+w[i])flag=1;
if(flag==1)cout<<"存在负权回路"<<endl;
#python代码乱入
#定义邻接矩阵 记录各城市之间的距离
weight = [[INF if j!=i else 0 for j in range(N)] for i in range(N)]
#判断负权回路
for i in range(N):
for j in range(N):
if dist[j] > dist[i] + weight[j][i]:
raise ValueError("存在负权回路")
#松弛n-1次，因为最短路径的深度最多是n-1,n为结点数目
for i in range(N-1):
change = False
#分别遍历边的两个顶点，从而实现遍历所有边。
for j in range(N):
for k in range(N):
if dist[j] > dist[k] + weight[j][k]:
dist[j] = dist[k] + weight[j][k]
#记录更新该结点的结点编号
last_update[j] = k
#标记更改状态
change = True
#如果本轮未作出更改，说明已完成
if not change:
break
*贝尔曼福特算法的队列优化
每次仅对最短路的估计值发生变化的顶点的所有出边执行松弛操作。那么怎么知道当前哪些点的最短路径发生变化？用队列来维护这些点。
每次取队首顶点u，对u所有出边进行松弛操作，如果u->v的边使得v的最短路径变短且不再当前队列中，则将v放入队尾。同一个顶点同时在队列中出现多次时毫无意义的，所以需要一个数组来判重。当对u的所有出边松弛完毕后就将u出队。直至队列空为止。
for(i=1;i<=m;i++)
{
scanf("%d %d %d",%u[i],&v[i],&w[i]);
//建立邻接表的关键，新来的边变成第一条边，之前的边挪到下一条边。
next[i]=first[u[i]];
first[u[i]]=i;
}
que[tail++]=1;
book[1]=1;
while(head<tail){
k=first[que[head]];
while(k!=-1){
if(dis[v[k]]>dis[u[k]]+w[k])//u,v,w定义同dijkstra那节
//u[i]起点的最短路径+其相连的边权值是否比现在v[i]终点最短路径小
{ dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0)
{
que[tail++]=v[k];
book[v[k]]=1;
}
}
k=next[k];
}
book[que[head]]=0;
head++;//出队
}
与bfs区别在于bfs的顶点出队后就不会再重新进入队列；而这里的顶点很可能在出队之后再次被放入队列。当一个节点最短路径变小后，需要对其所有出边进行松弛，保证相邻节点的最短路径同步更新。
队列优化后的算法时间复杂度最坏情况下也是o(nm)
队列优化后的算法如何判断是否有负权回路？当某个节点进入队列次数超n次则必然存在负环。
这个算法关键的地方在于只有在前一遍松弛中改变最短路径的顶点才可能引起它们的邻接点的最短路径改变。
