优质bellman_ford,spfa题解(HMZ发布)

题意

求一个图的某一个点到其他所有点的最短路长度

思路

存储

不可以用邻接矩阵,因为$n≤10^4$,可能会$MLE$

我的做法是邻接表

dijkstra(普通版)

参考 OI WiKi - dijkstra

对于每个点,分两步

• 求出整个图中最短路长度最短的点
• 将这个点所有连接的边标记为最短的长度^[1]

直到没有最短路可更新

dijkstra(优化版)

"求出整个图中最短路长度最短的点"这一段话是指目前已探索的点的最短路径最小的点

不如使用优先队列优化

对于每个点,分两步

• 获取队列顶的点
• 弹出
• 将这个点所有连接的边标记为最短的长度
• 将这个点如队列

直到队列没有元素

tips:

• 因为优先队列是从大到小,所以要调整

  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

如果你记不住,也许你可以这样想

将距离改为相反数再入队列

优先队列

与普通队列不同的是可以排序数据,从大到小!!!

可以

• push() 推入元素
• pop() 弹出元素
• top() 返回队列的顶部
• size() 返回队列长度

数据

$1≤n≤10^4,1≤m≤5×10^5,w>0,∑w<2^{31}$

$2147483647=2^{31}-1$

代码(普通版)

#include<iostream>
#include<vector>
#define INF 2147483647
#define N 11451
using namespace std;
int n,m,s;
struct node
{
    int v,l;//下一个点,边权
};
vector<node>g[N];//图
int len[N]={0};//记录最短路
int vis[N]={0};//标记数组
void dijkstra()
{
	for(int i=1;i<=n;i++)
	{
		int u=-1,mi=INF;//初始值注意!
		for(int j=1;j<=n;j++)
		{
			if(!vis[j] && len[j]<mi)//最短路最短的点
			{
				u=j;//记录
				mi=len[j];
			}
		}
		if(u==-1)//没有可以更新的点
		{
			return;
		}
		vis[u]=1;//标记
		for(int j=0;j<g[u].size();j++)//每下一个点
		{
			int v=g[u][j].v;
			if((!vis[v]) && len[u]+g[u][j].l<len[v])//发现有更短的路
			{
				len[v]=len[u]+g[u][j].l;//更新
			}
		}
	}
}
int main()
{
	fill(len,len+N,INF);//全部设为INF(2147483647)
    cin>>n>>m>>s;//输入
    len[s]=0;//初始距离
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;//输入
        g[u].push_back({v,w});//添加边
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
    	cout<<len[i]<<" ";//输出
	}
    return 0;//完结散花
}

代码(优化版)

#include<bits/stdc++.h>
#define INF 2147483647
#define N 114514
using namespace std;
int n,m,s;
struct node
{
    int v,w;
};
vector<node>g[N];
int d[N];
int vis[N];
priority_queue<pair<int,int> >q;//使用队列优化
void dijkstra()
{
    while(q.size())//注意这里
    {
        int u=q.top().second;//取出队列顶
        q.pop();//出队列
        vis[u]=1;//标记
        for(int j=0;j<g[u].size();j++)
        {
            int v=g[u][j].v;
            int w=g[u][j].w;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;//更新
                q.push({-d[v],v});//入队列
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        d[u]=INF;
        d[v]=INF;
    }
    d[s]=0;
    q.push({-d[s],s});//初始值
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}