2024寒假集训Day2

I am very “happy”.

今天学了Dijkstra算法、Bellman-Ford算法 and SPFA算法
是用来求解单源最短路径的。
(Floyd是求多源的最短路径）

1.Dilkstra

首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，以此类推，直到从源点v0到其他各个顶点的最短路径全部被求出为止。———来自PPT

• 找dis数组中最小的数（且s[i]!=1）
• 将s[i]设为1
• 如果dis[j]v[i]（权值为w[i]）这条边，使源点到vi号顶点的距离变短。即源点到u[i]号顶点的距离（dis[u[i]]） 加上 u[i]->v[i]这条边（权值为w[i]）的值是否比原来源点到v[i]号点距离（dis[v[i]]）要小——PPT

for(int k=1;k<=n-1;i++)//遍历n-1次，每个点都有可能和n-1个点连接 
{
    for(int j=1;j<=m)//对每组数组都做一次松弛 
    {
        if(dis[v[i]<dis[u[i]]+w[i])//判断经过一个中转点后是否路径更短 
        {
            dis[x[i]]=dis[u[i]]+w[i]; //是的话更新数据 
            path[v[i]]=path[u[i]]; //记录终点的前驱（上一个点），方便后面倒序输出 
        }
    }
}

注：不含回路，回路没有最短路径

3.SPFA

要用队列，不是很懂实现
思想是基与上一个算法而改进的

4.不知道什么东西

今天有学长来交流信息学的问题
就这样，没了