备战蓝桥杯---图论之最短路dijkstra算法

目录

先分个类吧：

1.对于有向无环图，我们直接拓扑排序，和AOE网类似，把取max改成min即可。

2.边权全部相等，直接BFS即可

3.单源点最短路

从一个点出发，到达其他顶点的最短路长度。

Dijkstra算法：用于一个节点到所有其他节点的最短路。（要求：不存在负权边，可以用于无向图）

---

先分个类吧：

1.对于有向无环图，我们直接拓扑排序，和AOE网类似，把取max改成min即可。

2.边权全部相等，直接BFS即可

3.单源点最短路

从一个点出发，到达其他顶点的最短路长度。

基本操作：松弛：d[u]+w<d[v]，于是距离更改。

Dijkstra算法：用于一个节点到所有其他节点的最短路。（要求：不存在负权边，可以用于无向图）

具体过程：

1.开始之前，认为所有点都未计算，dis[]全部赋为极大值。

2.源点的dis[]=0;

3。计算与源点相邻的所有点的dis=map[s][v];

4.在还未算出最短路点的dis中选出最小一个点u,显然，因为不存在负权边，它的最短路就是dis.

5.对于与u相连的所有点v若dis[u]+map[u][v]比当前的dis小就松弛更新。

6.重复上述4，5操作。

正确性证明：

其实就是每一次贪心，显然，从源点开始的第一步得到的最短的路肯定就是最短路（到它的其他路肯定比它长）。

当我们把除源点外第一个确定的加入后，我们再用它去更新一下它连的点。

然后，我们选其中最小的点，它就是确定的。因为，要走到它，要么从那些没有确定最小路的点出发到它（因为这点是最小的点+无负权边，因此这样的点距离肯定更大），要么从已经确定的点上拓展出来，又因为他们不断地更新松弛（每一个确定最小路的点加入后，我们再用它去更新一下它连的点），所以我们可以保证在已经确定地点到最小的点的路径是最优的。因此，我们保证最小的点它就是确定的。

下面放一道模板题：

下面是AC代码（注意，无向边建图edge要2倍）：

#include<bits/stdc++.h>
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
void merge(int x,int y,int v){edge[++cnt].zhi=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
priority_queue<ty> q;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].zhi){dis[i1]=dis[ck.dian]+edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cin>>n>>m1>>s>>t;memset(head,-1,sizeof(head));for(int i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]=0;cout<<dij(s,t);
}