最短路（SPFA版）

最短路有很多种解决方案，如SPFA、Floyd、Dijstra、A*等。接下来我就介绍SPFA。

1.简介

SPFA是一种用BFS来求最短路的解决方案，与 Dijstra、A*一样。总体步骤只有一个：bfs。

2.代码

1.bfs

/*变量等定义我省略了，只显示核心代码，欢迎在评论区打出这里的代码！*/
void bfs(){
	queue<int> q;
    bool val[100005];
    int dis[100005];
    
    for (int i = 1; i <= n; i++)
    {
    	dis[i]=1e9;
    }
    
    dis[s] = 0;//s为初始节点
    q.push(s);
    val[s]=true;
    
    while(!q.empty()){
    	int t= q.front();
        q.pop();
        
        val[t]=false;
        
        for (int i = 0; i < a[t].size(); i++){//a为结点vector
        	if (dis[a[t][i].first] > dis[t] + a[t][i].second){//判断
            	dis[a[t][i].first] = dis[t] + a[t][i].second;
                
                if (val[a[t][i].first]) continue;
                
                val[a[t][i].first]=true;
                q.push(a[t][i].first);
            }
        }
    }
}

//main
cin >> n >> m >> s;

for (int i = 1; i <= m; i++){
	int x, y, z;
    cin >> x >> y >> z;
    a[x].push({y,z});
}

bfs();

for (int i = 1; i <= n; i++)
{
	if (1e9 != dis[i]) cout << dis[i] << " ";
    else cout << -1 << " ";
}

cout << endl;

这就是SPFA的全部了，点个赞呗。欢迎在评论区留言！