暴力—时间复杂度O(n^2)
int ne[N],h[N],idx,e[N],wt[N];//wt[]表示边权
void add(int u,int v,int w) //链式前向星存图
{
idx++;
e[idx]=v;
wt[idx]=w; //边权
ne[idx]=h[u];
h[u]=idx;
}
int vis[N]; //vis[i]表示i点是否在s集合中
int d[N]; //d[i]表示 s->i 的最短路径
int p[N]; //p[i]表示i点是从哪个点过来的
void dijkstra(int s)
{
for(int i=1;i<=n;i++)
{
d[i]=INF;
//如果多次求d
//要更新vis[]
//要更新p[]
}
d[s]=0;
//执行n次把点从t集合到s集合
for(int i=1;i<=n;i++)
{
//1,找到最短路u
int u;
int minn=INF;
for(int j=1;j<=n;j++)
{
//s集合与t集合的最短边
if(d[j]<minn&&vis[j]==0)
{
u=j;
//把最小值的下标给u
minn=d[j];
//把最小值给minn
}
}
//2,把u移到s集合中
vis[u]=1; //移到s集合中
//3,在t集合中,跟u相邻的点进行松弛操作
for(int j=h[u];j;j=ne[j])
{
int v=e[j];
int w=wt[j];
if(vis[v]==0&&d[v]>d[u]+w)
{
d[v]=d[u]+w;
p[v]=u;//到达v的路径是从u来的
}
}
}
}
优先队列—时间复杂度O(mlogm)
struct node
{
int to;
int we;
};
vector<node >g[N];
bool vis[N];
int d[N];
//点u,d[u]
struct vnode
{
int p;//点
int d;//距离
bool operator< (const vnode&b) const//小顶堆——重载运算符
{
return d>b.d;
}
};
void dijkstra(int s)
{
priority_queue<vnode > q;
for(int i=1;i<=n;i++)
{
d[i]=INF;
}
d[s]=0;
q.push({s,0});
while(!q.empty())
{
int u=q.top().p;//找顶堆元素
q.pop();
if(vis[u]) //如果已经找到了，就不用再操作了
{
continue;
}
//如果在s集合中，就不用操作了，只有在t集合中，我们才拿进去，然后松弛
vis[u]=1;
for(auto e:g[u])
{
int v=e.to;
int w=e.we;
if(vis[v]==0&&d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push({v,d[v]});
}
}
}
}