今天的讲座学姐讲了三种算法，分别为:"Dijkstra","Bellman-ford"以及“Bellman-ford”的升级版—-"SPFA"(但"SPFA"需要采用队列，不太会)，这三种都和昨天的"Floyd"不大一样，"Floyd"是多源最短路径（计算任意个点对之间的最短路），而今天的这三种是单源最短路径（固定一个顶点为原点，求源点到其他每个顶点的最短路径）

首先是”Dijkstra”（注意边权值非负）

问题的提出：给定一个图G和源点v0，求v0到G中其他每个顶点的最短路径。限定各边上的权值非负。

大概思路：为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。基于贪心思想，时间复杂度为O(N²),首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，以此类推，直到从源点v0到其他各个顶点的最短路径全部被求出为止

基本定义：设置两个顶点的集合S和T：其中S中存放已找到最短路的顶点，初始时，集合S只有一个顶点，即源点v0。则T中存放当前还未找到最短路径的顶点。然后设置3个数组分别为
dis[ i ]：表示i点到源点v0的最短路长度，初始化dis[i]=e[v0][i];
S[ i ]：为0表示顶点i还未加入S， S[i]为1表示i已经加入S中，初始化S[v0]为1，其余为0，表示最初集合S中只有源点v0；
path[ i ]:表示v0到i的最短路径上顶点i的前一个顶点序号（即前驱）。 通过这个数组可以确定v0到i的最短路径上的每一个顶点

三步骤：
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]]）要小。

上代码

const int N = 1001;
int n, m;
int g[N][N];
int dist[N];
bool st[N];//定义

scanf("%d%d", &n, &m);
  memset(g, 0x3f, sizeof g);
  while(m --){
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c);
      g[a][b] = min(g[a][b], c);
    }//输出

int dijkstra(){
    memset(dist, 0x3f, sizeof dist); //dist数组初始化为无穷大
    dist[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1; //初始化为表示还没有确认，在下面的循环中找到dis最小且还没被标记过的点
        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中转
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}//主函数

优化：要用"堆"，好吧，不会

“Bellman-ford”（注意但无法处理存在负权回路的情况）

基本概念：同样是用来计算从一个点v0到其他所有点的最短路径的算法，也是一种单源最短路径算法。
其优于Dijkstra算法的方面是边的权值可以为负数、实现简单 。
算法时间复杂度：O(NM)，N是顶点数，M是边数。

算法实现：第1轮在对所有的边进行松弛之后，得到的是从1号顶点“只能经过一条边”到达其余各顶点的最短路径长度。
第2轮在对所有的边进行松弛之后，得到的是从1号顶点“最多经过两条边”到达其余各顶点的最短路径长度。如果进行k轮的话，得到的就是1号顶点“最多经过k条边”到达其余各顶点的最短路径长度。
只要进行n – 1 轮就可以了，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边。

上代码

//主代码
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];
        }               
}

//小优化
for(k=1;k<=n-1;k++)                 //进行n-1轮松弛
{   
    int flag=0;
     for(i=1;i<=m;i++)                   //枚举所有边
          if(dis[u[i]]+w[i]<dis[v[i]])   //u[i]、v[i]分别是这条边连接的两个点
           {
               dis[v[i]]=dis[u[i]]+w[i];
       flag=1;
           }
      if(flag==0) break;
}

//检测负权回路
void  huilu()
{   
       for(i=1;i<=m;i++)
       {
    if(dis[u[i]]+w[i]<dis[v[i]])
           return 1;             //存在负权值回路 
       }
       return 0;                //不存在负权值回路 
}

最后是”SPFA”

因队列不太会，因此不会

总结

今天过的依旧充实，明天继续加油！！！！！！！！！