图论算法----最短路-白红宇

图论算法----最短路

阅读量：6902 次

发布时间：2019-06-27

本文共 3506 字，大约阅读时间需要 11 分钟。

经典算法

单源最短路：

1.Bellman_ford（可判负环，可有负边）

d[i]表示起点S到i的最短路，那么d[i]=min{d[j]+w[j][i]}且存在j->i的边代价为w[j][i]

经过证明如果不存在负圈最多通过V-1次松弛就可以完成复杂度O(V*E)(V为结点数，E为边数)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #define maxn 5001010 #define maxm 10001011 #define INF 0x3fffffff12 using namespace std;13 struct edge{14 int from,to,w;15 edge(){}16 edge(int _u,int _v,int _w){17 from=_u,to=_v,w=_w;18 }19 };20 edge G[maxm];21 int V,E;22 void addedge(int u,int v,int w){23 G[E++]=edge(u,v,w);24 }25 int d[maxn];26 int n,m;27 //d[i] = min{d[j]+w[j][i]} {j->i}28 void bellman_ford(int s){29 V=n;30 for(int i=0;i
              
               d[e.from]+e.w){37 d[e.to] = d[e.from]+e.w;38 flag = true;39 }40 }41 if(!flag)break;42 }43 }44 int main (){45 while(scanf("%d%d",&n,&m)!=EOF){46 if(n==0&&m==0)break;47 int u,v,w;48 E=0;49 for(int i=0;i

View Code

判负环：看一下是不是多于V-1次松弛，如果有则存在负环

1 bool HaveNagativeLoop(){ 2     memset(d,0,sizeof(d)); 3     for(int i=0;i
      
       d[e.from]+e.w){ 7                 d[e.to] = d[e.from]+e.w; 8                 if(i==V-1)return true; 9             }10         }11     }12     return false;13 }

View Code

2.dijkstra(无负边)

对于上述的d[i]=min{d[j]+w[j][i]}如果d[j]当前值不是d[j]能达到的最小值那么显然在后面d[i]还将更新，如何避免这种情况

选择d[j]已经是最小，即S->j的最短距离不再更新，如何选取？每次选择距离最短且未被使用的结点，用这个结点对其他节点进行松弛复杂度O(V*V)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #define maxn 101010 #define maxm 10001011 #define INF 0x3fffffff12 using namespace std;13 //d[i]=min{d[j]+w[j][i]} {d[j]已经不再更新}14 //每次找最小d[j]然后松弛15 int G[maxn][maxn];16 int d[maxn];17 bool used[maxn];18 int V;19 void dijksta(int s){20 for(int i=0;i

View Code

来优化一下上面的算法，每次需要选择最短的一个结点，这个可以使用一个优先队列来维护当前所有边里面权值最小的边，所以算法复杂度变为O(V*log(E))

使用邻接表存储图比较容易写

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #define maxn 101010 #define maxm 10001011 #define INF 0x3fffffff12 using namespace std;13 struct edge {14 int to,w;15 edge(){}16 edge(int _to,int _w){17 to=_to;w=_w;18 }19 };20 typedef pair
              
                P;21 int V;22 vector
               
                 G[maxn];23 int d[maxn];24 void dijkstra(int s){25 priority_queue
                
                 ,greater
                  >q;26 for(int i=0;i
                  
                   d[v]+e.w){37 d[e.to]=d[v]+e.w;38 q.push(P(d[e.to],e.to));39 }40 }41 }42 }43 int main (){44 int n,m;45 while(scanf("%d%d",&n,&m)!=EOF){46 for(int i=0;i

View Code

3.floyd(任意两点的最短路，可有负边)

dp的思想 d[k+1][i][j]表示从0~k 里面选择中间结点从i到j的最短距离那么当k为-1时d[0][i][j]=w[i][j]

考虑如何转移从0~k-1中间选到0~k中选新的方案有两种情况：

不经过第k个结点那么 d[k+1][i][j]=d[k][i][j]

经过第k个结点那么d[k+1][i][j] = d[k][i][k]+d[k][k][j]

则方程为d[k+1][i][j]=min{ d[k][i][j]，d[k][i][k]+d[k][k][j]}

可以使用滚动数组来优化空间，由于d[k+1][][]只与d[k][][]有关，所以只要保证k是从小到大枚举的就可以节省以为空间，复杂度为O(V*V*V)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #define maxn 101010 #define maxm 10001011 #define INF 0x3fffffff12 using namespace std;13 int d[maxn][maxn];14 int V;15 void init(int n){16 V=n;17 for(int i=0;i

View Code

转载于:https://www.cnblogs.com/shuzy/p/3776575.html

你可能感兴趣的文章