这里我确实应该反思一下，今天都已经要上战场的时候了，发现我很多关于这种经典的算法甚至都没有整理过，顶多只是知道原理，因此在看到队友的博客之后也是想把这一部分顺便再写一下吧。
Dijkstra
算法的基本思想是：每次找到离原点最近的一个顶点，以该顶点为中心进行拓展，最终得到原点到其余点的最短路径
步骤如下：将所有顶点分成两部分，已收录与未收录，从未收录中找到距离原点最近的一个点，以该点更新与其相连的所有点，收录此点，以此类推，注意，收录之后需要标记此点已收录，因为它已经松弛过了邻接点，所以不用再次访问。
题目举例（洛谷P4779）
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define lt x<<1
#define rt x<<1|1
#define pii pair<int,int>
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
int n,m,s;
int head[maxn],cnt,d[maxn],vis[maxn];
struct Node{
int next,to,val;
}edge[maxn];
void add_edge(int from,int to,int w)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].val=w;
head[from]=cnt;
}
void dijkstra()
{
priority_queue<pii,vector<pii>,greater<pii> > qu;
d[s]=0;
qu.push({d[s],s});
while(!qu.empty())
{
pii t=qu.top();
qu.pop();
int u=t.second;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i!=0;i=edge[i].next)
{
int v=edge[i].to;
if(d[v]>d[u]+edge[i].val)
qu.push({d[v]=d[u]+edge[i].val,v});
}
}
}
int main()
{
cin>>n>>m>>s;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
}
memset(d,inf,sizeof(d));
dijkstra();
for(int i=1;i<=n;i++)
{
printf("%d ",d[i]);
}
printf("\n");
return 0;
}
最小生成树
这里的两种算法都以同一道模板题目来进行总结，选用的都是（洛谷P3366）。
Kruskal
算法Kruskal是解决最小生成树的常用算法（这里的小根据题目的定义来，可能是距离或者权值等），其基本思路是边上的贪心，每次选择未被收录的长度最小的边，将其加入集合，直到无边可选，设边数为M，点数为N，Kruskal的时间复杂度为 O ( M l o g M ) O(MlogM) O(MlogM)，也就是说，不适宜边多的情况。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lt x<<1
#define rt x<<1|1
#define pii pair<int,int>
const int maxn = 2e5+10;
const int N=5005;
const int inf = 0x3f3f3f3f;
int n,m,s;
int u,v,w;
int fa[N];
int cnt;
struct Node
{
int from,to,val;
bool operator>(const Node b) const
{
return val>b.val;
}
bool operator<(const Node b) const
{
return val<b.val;
}
};
priority_queue<Node,vector<Node>,greater<Node> > qu;
int Seek(int x)
{
return x==fa[x]?x:fa[x]=Seek(fa[x]);
}
void Union(int x,int y) //并查集合并
{
int fx=Seek(x),fy=Seek(y);
if(fx!=fy)fa[fx]=fy;
}
int Kruskal()
{
int ans=0;
while(!qu.empty())
{
Node zan=qu.top();
qu.pop();
if(Seek(zan.from)==Seek(zan.to))
continue;
Union(zan.from,zan.to);
ans+=zan.val;
cnt++;
if(cnt==n-1)
break;
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
fa[i]=i;
for(int i=1; i<=m; i++)
{
cin>>u>>v>>w;
qu.push({u,v,w});
}
int ans=Kruskal();
if(cnt==n-1)
cout<<ans<<endl;
else
cout<<"orz"<<endl;
return 0;
}
Prim
与Kruscal相反，Prim算法的主要操作对象是点，算法思想也是贪心，基本思路是选择到当前已构造的生成树的最小距离的点，将其收录，用该点更新其相邻节点到生成树的距离
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lt x<<1
#define rt x<<1|1
#define pii pair<int,int>
const int maxn = 2e5+10;//边数
const int N=5005;//点数
const int inf = 0x3f3f3f3f;
int n,m,s;
int u,v,w;
struct Node{
int next,to,val;
}edge[maxn<<1];//这里因为是双向存图，所以要开二倍空间
int head[N],cnt,acc=0,dis[N];
int vis[N];
void add_edge(int from,int to,int val)//链式前向星加边
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].val=val;
head[from]=cnt;
}
int Prim()
{
int ans=0;
memset(dis,inf,sizeof(dis));
priority_queue<pii,vector<pii>,greater<pii> > qu;//优先队列中存的值first表示边权，second表示连接的第二个点，即要扩展的点
dis[1]=0;
qu.push({0,1});
while(!qu.empty())
{
pii t=qu.top();
qu.pop();
int u=t.second;
if(vis[u])continue;
vis[u]=1;
ans+=dis[u];
acc++;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(vis[v])
continue;
if(dis[v]>edge[i].val)
{
qu.push({edge[i].val,v});
dis[v]=edge[i].val;
}
}
if(acc==n)
break;
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
int ans=Prim();
if(acc==n)
cout<<ans<<endl;
else
cout<<"orz"<<endl;
return 0;
}
