Today is the second training day

Extremely difficult but rewarding

又到了一天一度的写文章和总结一天的时候了

今天主要学了3种求一个原点到任意的一点的最短距离

Dijkstra（限定各边上的权值非负）———and———Bellman-Ford————and————SPFA (这个不太懂）

这三种都和昨天的"Floyd"不大一样，"Floyd"是多源最短路径（计算任意个点对之间的最短路），而今天的这三种是单源最短路径（固定一个顶点为原点，求源点到其他每个顶点的最短路径）

以及扩展了一个在Bellman-Ford上改进的一个SPFA算法

它们以及 Floyd 都各有长处以及各有不足

Floyd 是可以求出任意两点的距离

Dijkstra———Bellman-Ford 可以求出一个原点到任意的一点的最短距离Dijkstra———Bellman-Ford 可以求出一个原点到任意的一点的最短距离

相同点：都要找到他们的关联点和线，通过数组来完成相对应的工作

for(k=1;k<=n;k++)//中间点
    for(i=1;i<=n;i++)//起点
        for(j=1;je[i][k]+e[k][j])
//如果对于原先两点之间的权值还小的话
            {
                e[i][j]=e[i][k]+e[k][j];
//进行赋值
                path[i][j]=path[k][j];
            }   //大都是这个原理

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

三步骤：
1.在数组dis[ i ]里查找S[ i ]!=1，并且dis[ i ]最小的顶点k
2.将S[ k ]改为1，表示 k 已经加入S集合中。即已经找到源点v0到点k的最短路径了。
3.修改T集合中每个顶点 j 的dis和path数组元素值：当S[ j ]！=1，且k到顶点 j 有dis[ k ]+e[ k ][ j ] v[i]）权值为w[i]初始化：dis[v0]=0,dis[ i ]=∞（i≠v0） 看看能否通过u[i]—>v[i] （权值为w[i]）这条边，使源点到vi号顶点的距离变短。即源点到u[i]号顶点的距离（dis[u[i]]） 加上 u[i] —> v[i]这条边（权值为w[i]）的值是否比原来源点到v[i]号点距离（dis[v[i]]）要小。

dist[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1; 
//初始化，标记
        for(int j = 1; j  dist[j]))
         {
                t = j;
            }
        }
        st[t] = true;
    //标记点t已经找到最短路径了
        for(int j = 1; j <= n; j ++){
  dist[j] = min(dist[j], dist[t] + g[t][j]);
        //通过点t中转
        }
    }

Bellman-Ford：更加方便，一步一步的进行松弛，最终完成总计算。但是由于计算线，所以不能有回路。（线）（最多进行n – 1 次（n为点数））

for(k=1;k<=n-1;k++)
//进行n-1轮松弛
{
    for(i=1;i<=m;i++)   
//枚举所有边，判断能否松弛
        if(dis[u[i]]+w[i]<dis[v[i]])
        {
            dis[v[i]]=dis[u[i]]+w[i];
            path[v[i]]=u[i];
        }               
}

这就是今天study的content
Thank you very much for taking the time to watch my content.
Good bye