最短路

冷不防 2021-11-02 14:24 466阅读 0赞

复习下图论算法

1. 邻接表的Dijkstra

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//邻接表存储图的最短路 
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    
    #define MAXN 100100
    struct Edge
    {
      int u, next, val;
      Edge() {}
      Edge( int v , int Next ,int Val): u(v),next(Next), val(Val) { }      
    }edge[MAXN];
    
    const int inf = 0x7f7f7f7f;
    int head[MAXN],dis[MAXN], visit[MAXN], size, S, T, N, M;
    
    void init( )
    {
      for( int i = 0; i < MAXN; i++)
           head[i] = -1;
      size = 0;     
    }
    
    void AddEdge( int u, int v, int val)
    {
       edge[size] = Edge( v, head[u], val);
       head[u] = size++;
       
       edge[size] = Edge( u, head[v], val);
       head[v] = size++;
         
    }
    
    
    int dij( )
    {
       for( int i = 1; i <= N; i++)
       {
            dis[i] = inf;
            visit[i] = 0;
       }
       for( int e = head[S]; e != -1; e = edge[e].next )
       {
          
            int v = edge[e].u;
            int w = edge[e].val;
            dis[v] = w;          
            
       }
       visit[S] = 1;
       dis[S] = 0;
       for( int i = 1; i <= N; i++)
       {   
           int oo = inf, k;
           for( int j = 1; j <= N; j++)      
           {
              if( !visit[j] && dis[j] < oo )
              {
                 oo = dis[j];
                 k = j;
                  
              }     
           }
           visit[k] = 1;
           for( int e = head[k]; e != -1; e = edge[e].next)
           {  
              int v = edge[e].u;
              int w = edge[e].val;
              if( !visit[v] && dis[v] > dis[k] + w && dis[k] != inf)
              {
                    dis[v] = dis[k] + w;    
                  
              }  
                
           }
       }
       return dis[T];
    } 
            
    
        
        
    
    int main( )
    {
      int a, b, c;
      while( scanf("%d%d", &N, &M), N + M)
      {
         init( );
         for( int i = 1; i <= M; i++)
         {
             scanf("%d%d%d",&a, &b, &c);
             AddEdge(a, b, c);   
         } 
         S = 1;
         T = N;      
         printf("%d\n", dij());
      }      
      return 0;  
    }

2. 邻接表 + 优先队列 + Dijkstra

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//邻接表存储图的最短路 
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <iostream>
    #include <queue>
    using namespace std;
    
    #define MAXN 100100
    struct Edge
    {
      int u, next, val;
      Edge() {}
      Edge( int v , int Next ,int Val): u(v),next(Next), val(Val) { }      
    }edge[MAXN];
    
    const int inf = 0x7f7f7f7f;
    int head[MAXN],dis[MAXN], visit[MAXN], size, S, T, N, M;
    
    
    struct node
    {
      int ID,dis;
      bool operator < ( const node &A) const 
      {
          return dis < A.dis;     
           
      }
    };
    
    void init( )
    {
      for( int i = 0; i <= N; i++)
      {
           head[i] = -1;
           visit[i] = 0;
           dis[i] = inf;
      }
      size = 0;
           
    }
    
    void AddEdge( int u, int v, int val)
    {
       edge[size] = Edge( v, head[u], val);
       head[u] = size++;
       
       edge[size] = Edge( u, head[v], val);
       head[v] = size++;
         
    }
    
    //优先队列优化 
    int dij( )
    {
       priority_queue<node>q;
       node p;
       p.ID = S;
       p.dis = 0;
       q.push(p);
       dis[S] = 0;
       while( !q.empty( ))
       {  
           p = q.top( );
           q.pop();
           int v = p.ID;
           int wx = p.dis;
           if( wx != dis[v] ) continue;  
           for( int e = head[v]; e != -1; e = edge[e].next)
           {  
              int u = edge[e].u;
              int w = edge[e].val;
              if( dis[u] > wx + w )
              {
                    dis[u] = wx + w;    
                    p.ID = u;
                    p.dis = dis[u];
                    q.push( p );
              }  
                
           }
       }
       return dis[T];
    } 
            
    
        
        
    
    int main( )
    {
      int a, b, c;
      while( scanf("%d%d", &N, &M), N + M)
      {
         init( );
         for( int i = 1; i <= M; i++)
         {
             scanf("%d%d%d",&a, &b, &c);
             AddEdge(a, b, c);   
         } 
         S = 1;
         T = N;      
         printf("%d\n", dij());
      }      
      return 0;  
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/10/2584002.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/0fbebd856de442ca9bba5ba313049f5d.png