floyd

(写给自己看)最短路系列

dijkstra算法

思想

• 无负权的单源最短路
• 每次扩展的是最短路径的点
• priority_queue<node> 可轻松实现,同一节点可能有不同距离在队列中，但每次出优先队列都是最小的，也就是最短距离

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include
        
         #include
         
          #include
          
           using namespace std;//author:fridayfang//date:19 2月 27//global varibles#define ll long long;#define inf 0x3f3f3f3f#define CL(a,b) memset(a,b,sizeof(a))#define sf(a) scanf("%d",&a)#define pr(a) printf("%d\n",a)#define db(a) printf("db %d\n",a)#define fr0(i,m) for(int i=0;i
           
            n2.di; }};int dij(int r){ CL(dis,0x3f); priority_queue
            
              q; dis[r]=0,q.push(Node(r,dis[r])); int cntn=0; while(!q.empty()){ Node tmp=q.top(); q.pop(); int idx=tmp.idx; if(idx==b) return dis[idx]; for(int t=head[idx];t!=-1;t=es[t].nxt){ int v=es[t].v,w=es[t].w; if(dis[idx]+w
            
           
          
         
        
       
      
     
    

bellmanford

思想

• 类似动态规划,求不超过\(0,1,2..(n-1)\)条边的最短路径
• 每次枚举E条边\(<u,v>,dis[v]<dis[u]+w[u][v]\) 则更新dis[v]
• 可判负环，\(n-1\)此后还能松弛则有负权环 O(E*V)

• 优化算法 SPFA

  维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个

  源点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代，取出队头的点v，依次枚举从v出发的边v->u， 若

Dist[v]+len(v->u) 小于Dist[u]，则改进Dist[u]（可同时将u前驱记为v）。

此时由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在

队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所

有节点的最短距离都确定下来，结束算法。 若一个点最短路被改进的次数达

到n ，则有负权环(原因同B-F算法） 。 可以用spfa算法判断图有无负权环

在平均情况下， SPFA算法的期望时间复杂度为O(E)

• (这个好像是最长路，例题不太好)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include
        
         #include
         
          #include
          
           using namespace std;//author:fridayfang//date:19 2月 27//global varibles#define ll long long;#define inf 0x3f3f3f3f#define CL(a,b) memset(a,b,sizeof(a))#define sf(a) scanf("%d",&a)#define pr(a) printf("%d\n",a)#define db(a) printf("db %d\n",a)#define fr0(i,m) for(int i=0;i