一、Bellman-Ford算法 

        算法思想：通过 n 次循环，每次循环都遍历每条边（共 m 条边），进而更新节点的距离，每次循环至少可以确定一个点的最短路，循环 n 次，求出 n 个点的最短路

        时间复杂度 ：   （n为节点个数，m为边总数）

        与前面所述的dijkstra算法不同，Bellman-Ford 算法可以处理含负权边的单源最短路问题，同时可以判断是否存在负权回路。

        算法描述：

        ①初始化：将除起始点 s 以外的 dis 数组设置为 无穷大， dis[ s ] = 0

        ②迭代：遍历图中的每条边，对边的两个顶点分别进行松弛操作，一共遍历 n 次 m条边，直到没有节点能够松弛

        ③判断负环：Bellman-Ford算法迭代后，再迭代一次，若最短路距离发生改变，则存在负环。

        核心代码：

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
    int u=edge[i].u;
    int v=edge[i].v;
    int w=edge[i].w;
  	 if(dist[u]+v<dist[v])
  	   dist[v]=dist[u]+w; //松弛
}

应用

        Bellman-Ford算法，第 i 次循环 m 条边时，可以确定走 i 条路到达的点的最短距离。 当图为一条直线时，需要 n-1 次循环即可确定最短路。

求有边数限制的最短路

        通过上述 Bellman-Ford算法思路，若求 k 条边数限制的最短路，仅需要循环 k 次 m条边，以下图举例说明。

        

    k = 1 时，通过上述代码，遍历一次即可算出 节点2 3 的最短路，但是这是错误的。当边的顺序为 (2,3,3)  (1,2,2) 时，遍历一次仅可以求出 节点2 的最短路，说明上述仅遍历一次得出的 节点3 不一定是最短路。

    考虑原问题，若需要求 k 条边限制的最短路

     通过第一种情况边的顺序可以得出 dis[ 3 ] 为 5 ，可是显然仅走1条边时到达不了节点3

     而通过第二种情况边的顺序又可以得出正确结果。但是当节点数明显增多时，边的顺序无法自行更改，应该如何处理？

        进行备份，保存其上一[2] 应为第0条边时的值（正无穷），同时将备份数组不断更新。层的状态，对该状态进行松弛操作（即当考虑第k条边时，对其考虑第 k-1 条边的状态进行松弛操作），在上述图例中，当对 节点3 进行松弛操作的 dis

        此外，当存在负权边时，仍然会更新，可是更新后的大小为 正无穷+负权值，在最后判断是否到达该节点时仅需判断 

if ( dist [n] > 0x3f3f3f3f/2 ) return -1;

核心代码：

memset(dis,0x3f,sizeof(dis));
dist[1]=0;
for(int i=1;i<=k;i++) 
{
    for(int j=1;j<=n;j++) bf[i]=dis[i];
	for(int j=1;j<=m;j++)   // 枚举所有边 
	{
		 int a=edge[j].a,b=edge[j].b,w=edge[j].w;	
		 dis[b]=min(dis[b],bf[a]+w); // 用备份更新 
	}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];

二、SPFA算法

        SPFA算法是在上述 Bellman-Ford 基础上优化得来的，Bellman-Ford中，当某个点未被更新过，仍会用该点去更新其他节点，这是无意义的，使得效率降低，SPFA中将更新后的节点再去更新其他节点即可。

void spfa()
{// 将更新的节点加入队列中，队列中的元素即为已更新的节点
	memset(dis,0x3f,sizeof(dis));
	dist[1]=0;
	queue<int>q;
	q.push(1); //入队 
	st[1]=1; // 队列中含有该节点
	while(q.size()) // 队列不空
	{
	   int u=q.front(); 
	   q.pop();
	   st[u]=0; // 出队
	   for(int i=head[u];i!=-1;i=edge[i].next)
	   {
	   	 int v=edge[i].v;
	   	 int w=edge[i].w; 
         if(dis[v]>dis[u]+w)
	   	 {
	   	    dis[v]=dis[u]+w;
			if(!st[v])  //如果不在队列中，入队
			{
				q.push(v); 
				st[v]=1;		    } 	    	
		 }
	   }	
	} 
}

SPFA应用：判断负环

        负环：当图中存在一个环，使得绕环遍历一圈的结果为负数，这样绕该环一直遍历，最短距离不断减小，不存在最短路．

SPFA判断负环：用一个 cnt [x] 数组存储 起点到 x 点的最短路径经过的边数，因为SPFA为最短路算法，经过的边数一定＜n ,若 cnt 数组的某个值 >=n , 则说明存在负环。

        此外，通过链式前向星构建的图不一定是连通的，可能存在自环的情况(负自环)，因此需要首先将所有节点入队。

bool spfa()
{// 将更新的节点加入队列中，队列中的元素即为已更新的节点
	memset(dis,0x3f,sizeof(dis));
	dist[1]=0;
	queue<int>q;
    for(int i=1;i<=n;i++)
    {
	    q.push(i); //入队 
	    st[i]=1; // 队列中含有该节点
	}
    while(q.size()) // 队列不空
	{
	   int u=q.front(); 
	   q.pop();
	   st[u]=0; // 出队
	   for(int i=head[u];i!=-1;i=edge[i].next)
	   {
	   	 int v=edge[i].v;
	   	 int w=edge[i].w; 
         cnt[v]=cnt[u]+1;
         if(cnt[v]>=n) return true; // 经过边数>=n，存在负环
         if(dis[v]>dis[u]+w)
	   	 {
	   	    dis[v]=dis[u]+w;
			if(!st[v])  //如果不在队列中，入队
			{
				q.push(v); 
				st[v]=1;
		    } 	    	
		 }
	   }	
	} 
}

三、Floyd 算法

        Floyd 算法可以实现多源最短路,思想基于动态规划,从 节点i 到 节点j 的路径有两种：

        1.从 节点i 直接到 节点j  dis[i][j]=dis[i][j]

        2. 节点i 经过某些节点到达 节点k 再经过某些节点到达 节点j   dis[i][j]=dis[i][k]+dis[k][j] 

        通过上面两种方式进行更新

        时间复杂度为 

void floyd()
{
 for(int k=1;k<=n;k++)
   for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}