图的四种搜索方法
dijkstra 算法
代码原理：
通过已知的点更新未知的点：
if(!vis[y] && dis[y]>dis[x]+d){//判断是否更新
dis[y]=dis[x]+d;
Q.push({y,dis[y]});
}示例代码：
inline bool operator <(node a,node b){
return a.y>b.y;
}
inline void add(int x,int y,int z){
ver[++tot]=y,edg[tot]=z;
nxt[tot]=head[x],head[x]=tot;
}
inline void dij(int x){
priority_queue<node> Q;
Q.push({x,0});
memset(dis,0x3f,sizeof dis);//趋近于无穷大
dis[x]=0;
while(!Q.empty()){
int x=Q.top().x;Q.pop();
vis[x]=1;//标记
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],d=edg[i];
if(!vis[y] && dis[y]>dis[x]+d){//判断是否更新
dis[y]=dis[x]+d;
Q.push({y,dis[y]});
}
}
}
}适用情况：
dijkstra算法可行的条件是不存在负边权。
时间复杂度 O(n log)
spfa
实现原理：
计算所有的情况。 当有同样元素在队列中时，就不入队：
if(!vis[y] ){//如果有同样元素在队列里，就不入队。
vis[y]=1;//标记入队。
Q.push(y);
}对于全是正边权的图，我们可以使用dijkstra处理最短路问题。但是如果带有负边权，需考虑是否存在负权环，如果起点与终点的路径经过负权环，则没有最短路。dijkstra算法无法保证节点出队时一定得到最短路，需要重新寻找方法。
显然，spfa的复杂度会比dijkstra高，一般为：O(km),k是一个常数，在稀疏图中一般<=2。 但是要卡spfa也比较简单，只需尽可能多得让节点重复入队。最坏复杂度可以做到O(nm)。在使用时需要特别注意。
示例代码：
inline void add(int x,int y,int z){
ver[++tot]=y,edg[tot]=z;
nxt[tot]=head[x],head[x]=tot;
}
inline void spfa(int xx){
queue<int> Q;
Q.push(xx);
memset(dis,0x3f,sizeof dis);
dis[xx]=0;
while(!Q.empty()){
int x=Q.front();Q.pop();
vis[x]=0;//标记出队
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],d=edg[i];
if(dis[y]>dis[x]+d){
dis[y]=dis[x]+d;
if(!vis[y] ){//如果有同样元素在队列里，就不入队。
vis[y]=1;//标记入队。
Q.push(y);
}
}
}
}
}判断负环：
inline void add(int x,int y,int z){
ver[++tot]=y,edg[tot]=z;
nxt[tot]=head[x],head[x]=tot;
}
inline void spfa(int xx){
queue<int> Q;
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=n;i++) {
vis[i]=1;Q.push(i);
}
while(!Q.empty()){
int x=Q.front();Q.pop();
vis[x]=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i],d=edg[i];
if(dis[y]>dis[x]+d){
dis[y]=dis[x]+d,cut[y]=cut[x]+1;
if(cut[y]>n||YN){//判断是否便利超过n次
YN=1;return;
}
if(!vis[y] ){
vis[y]=1;
Q.push(y);
}
}
}
}
}适用情况：
带负边权的最短路
bellman_ford
实现原理：
| n | 1 | 2 | 3 |
|---|---|---|---|
| 1 | 0 | 无限 | 无限 |
| 2 | 0 | 2 | 无限 |
| 3 | 0 | 2 | 3 |
示例代码：
void bellman_ford(int x){
memset(dis,0x3f,sizeof dis);
dis[x]=0;
for(int i=1;i<=k;i++){
memcpy(odis,dis,sizeof dis);//复制数组
for(int j=1;j<=m;j++){
dis[l[j].y]=min(dis[l[j].y],odis[l[j].x]+l[j].w);
}
}
}判断负环：
bool bellman_ford(int x){
memset(dis,0x3f,sizeof dis);
dis[x]=0;
for(int i=1;i<n;i++){
memcpy(odis,dis,sizeof dis);//复制数组
for(int j=1;j<=m;j++){
dis[l[j].y]=min(dis[l[j].y],odis[l[j].x]+l[j].w);
}
}
for(int i=1;i<=m;i++){
if(dis[l[i].x]+l[i].w<dis[l[i].y]) return 0;
}
return 1;
}适用情况：
有边数限制的最短路、
复杂度为O(nm)
floyd
实现原理：
floyd本质上就是通过不断为两点的路径上增加中间点(所以又称为插点法)，进而对邻接矩阵进行更新迭代，每加入一个点，矩阵信息就可能变化一次，从而维护该最小距离矩阵。
如下：
if(l[i][j]>l[i][k]+l[k][j]){
l[i][j]=l[i][k]+l[k][j];
}
| 初始表格: | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | ∞ | 2 | |
| 2 | 1 | 0 | ∞ | 6 | |
| 3 | 8 | 3 | 0 | 11 | |
| 4 | ∞ | ∞ | ∞ | 0 |
| 加入1为中间点: | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | ∞ | 2 | |
| 2 | 1 | 0 | ∞ | ||
| 3 | 8 | 3 | 0 | ||
| 4 | ∞ | ∞ | ∞ | 0 |
| 加入2为中间点: | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | ∞ | 2 | |
| 2 | 1 | 0 | ∞ | ||
| 3 | 3 | 0 | |||
| 4 | ∞ | ∞ | ∞ | 0 |
示例代码：
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(l[i][j]>l[i][k]+l[k][j]){
l[i][j]=l[i][k]+l[k][j];
pre[i][j]=k;
}
}
}
}
}判断负环：
int floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(l[i][j]>l[i][k]+l[k][j]){
l[i][j]=l[i][k]+l[k][j];
}
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(l[i][j]>l[i][k]+l[k][j]){
return 1;
}
}
}
}
return 0;
}适用情况：
求任意两点之间的距离
时间复杂度：
“对于重要的事物，我们的眼光总是模糊不清。只有未来才能给予我们足够的远见。”————邓布利多