最短路复习

谁借莪１个温暖的怀抱￠ 2021-10-15 11:51 225阅读 0赞

HDU 1874

1.dijkstra 算法

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

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    const int inf = 0x7f7f7f7f;
    int mp[400][400];
    int visit[400];
    int dis[400];
    int S, T;
    
    void dij( int N )
    {
         
    for( int i = 0; i < N; i++)
      {
         
        visit[i] = 0;
        dis[i] = mp[S][i];
      }
      visit[S] = 1;
    for( int i = 0; i < N; i++)
      {
         
    int t = inf, k;
    for( int j = 0; j < N; j++)
        {
         
    if( !visit[j] && dis[j] < t)
          {
         
              t = dis[j];
              k = j;
          }
        }
        visit[k] = 1;
    for( int j = 0; j < N; j++)
        {
         
    if( !visit[j] &&mp[k][j] != inf && dis[j] > dis[k] + mp[k][j] )
            {
         
               dis[j] = dis[k] + mp[k][j];
            }
        }
      }
    if( dis[T] == inf )
        puts("-1");
    else
        printf("%d\n", dis[T]);
    }
    
    int main( )
    {
         
    int N, M, a, b, c;
    while( scanf("%d%d",&N, &M) != EOF)
      {
         
    for( int i = 0; i <= N; i++)
    for( int j = 0; j <= N; j++)
                mp[i][j] = ( i == j) ? 0 : inf;
    for( int i = 1; i <= M; i++)
        {
         
          scanf("%d%d%d",&a,&b,&c);
          mp[a][b] = mp[b][a] = min(mp[a][b],c);
        }
        scanf("%d%d",&S,&T);
        dij( N );
      }
    return 0;
    }

2.优先队列 + dijkstra

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

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <algorithm>
    #include <queue>
    using namespace std;
    struct node
    {
         
    int v, dis;
    bool operator < (node A) const
    {
         
    return dis > A.dis;
    }
    };
    const int inf = 0x7f7f7f7f;
    int S,T;
    int dis[400];
    int visit[400];
    int mp[400][400];
    priority_queue<node>p;
    
    
    void  pri_dij( int N )
    {
         
    for( int i = 0; i < N; i++)
      {
         
        dis[i] = mp[S][i];
        node q;
        q.v = i;
        q.dis = dis[i];
        p.push(q);
        visit[i] = 0;
      }
    while( !p.empty())
      {
         
         node q = p.top( );
         p.pop( );
    int u = q.v;
         visit[u] = 1;
    for( int i = 0; i < N; i++)
         {
         
    if( !visit[i] && dis[i] > dis[u] + mp[u][i] && dis[u] != inf )
           {
         
              dis[i] = dis[u] + mp[u][i];
              node qx;
              qx.v = i;
              qx.dis = dis[i];
              p.push(qx);
           }
         }
    
      }
    if( dis[T] == inf )
        puts("-1");
    else
        printf("%d\n",dis[T]);
    }
    int main( )
    {
         
    int N, M, a, b, c;
    while( scanf("%d%d",&N, &M) != EOF)
      {
         
    for( int i = 0; i <= N; i++)
    for( int j = 0; j <= N; j++)
                mp[i][j] = ( i == j) ? 0 : inf;
    for( int i = 1; i <= M; i++)
        {
         
          scanf("%d%d%d",&a,&b,&c);
          mp[a][b] = mp[b][a] = min(mp[a][b],c);
        }
        scanf("%d%d",&S,&T);
        pri_dij(N);
      }
    return 0;
    }

3.floyd-warshall算法

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

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    int mp[400][400];
    const int inf = 0x7f7f7f7f;
    int S, T;
    
    void floyd( int N )
    {
         
    for( int k = 0; k < N; k++)
    for( int i = 0; i < N; i++)
    for( int j = 0; j < N; j++)
    if( mp[i][j] > mp[i][k] + mp[k][j] && mp[i][k] != inf && mp[k][j] != inf)
                    mp[i][j] = mp[i][k] + mp[k][j];
    if( mp[S][T] != inf )
      printf("%d\n",mp[S][T]);
    else
      puts("-1");
    }
    
    int main( )
    {
         
    int N, M, a, b, c;
    while( scanf("%d%d",&N, &M) != EOF)
      {
         
    for( int i = 0; i <= N; i++)
    for( int j = 0; j <= N; j++)
                mp[i][j] = ( i == j) ? 0 : inf;
    for( int i = 1; i <= M; i++)
        {
         
          scanf("%d%d%d",&a,&b,&c);
          mp[a][b] = mp[b][a] = min(mp[a][b],c);
        }
        scanf("%d%d",&S,&T);
        floyd(N);
      }
    return 0;
    }

4. bellman-ford算法

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

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    
    using namespace std;
    int N, M, S, T;
    int dis[300];
    int mp[300][300];
    const int inf = 0x7f7f7f7f;
    
    void Init( )
    {
         
    for( int i = 0; i < 300; i++)
    for( int j = 0; j < 300; j++)
            mp[i][j] = ( i == j ) ? 0 : inf;
    }
    
    void Relax( int v, int u)
    {
         
    if( mp[u][v] != inf && dis[v] > dis[u] + mp[u][v] )
         dis[v] = dis[u] + mp[u][v];
    }
    
    void bell_manford(  )
    {
         
    for( int i = 0; i < 300; i++)
       {
         
         dis[i] = inf;    
       }
       dis[S] = 0;
    for( int n = 1; n < N; n++)
       {
         
    for(int u = 0; u < N; u++)
         {
         
    for(int v = 0; v < N; v++)
              Relax(v, u);
         }
      }
    if( dis[T] != inf )
      printf("%d\n",dis[T]);
    else
      puts("-1");
    }
    
    int main( )
    {  
    int a, b, c;
    while( scanf("%d%d",&N,&M) != EOF )
       {  
          S = 1;
          Init( );
    for( int i = 1; i <= M; i++)
          {
         
            scanf("%d%d%d",&a,&b,&c);
            c = min(mp[a][b],c);
            mp[a][b] = mp[b][a] = c;
          }
          scanf("%d%d",&S,&T);
          bell_manford( );
       }
    return 0;
    }

5。spfa算法

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

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    const int inf = 0x7f7f7f7f;
    typedef vector<int>::iterator It; 
    vector<int>p[400];
    int mp[400][400];
    int S, T;
    
    void spfa(int N)
    {
         
    for( int i = 0; i <= N; i++)
      {
         
         dis[i] = inf;
      }
      queue<int>q;
      q.push(S);
      dis[S] = 0;
    while( !q.empty() )
      {
         
    int u = q.front( );
         q.pop( );
    for(It iter = p[u].begin(); iter != p[u].end(); iter++)
         {
         
    if( dis[*iter] > dis[u] + mp[u][*iter] )
              {
         
                  dis[*iter] = dis[u] + mp[u][*iter];
                  q.push(*iter); 
              }
         }
      }
    if( dis[T] != inf )
       printf("%d\n",dis[T]);
    else
       puts("-1");
    }
    
    int main( )
    {
         
    int N, M, a, b, c;
    while( scanf("%d%d",&N, &M) != EOF )
      {  
    for( int i = 0; i <= N; i++)
          {
         
              p[i].clear( );
          }
    for( int i = 0; i <= N; i++)
    for( int j = 0; j <= N; j++)
               mp[i][j] = ( i == j) ? 0 :inf;
    for( int i = 1; i <= M; i++)
          {
         
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b] = mp[b][a] = min(mp[a][b], c);
            It iter1 = p[a].begin( );
            It iter2 = p[a].end( );
    if( find(iter1, iter2, b) == iter2 )
           {
         
              p[a].push_back(b);
              p[b].push_back(a);
           }
          }
          scanf("%d%d",&S,&T);
          spfa( N );
      }
    return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/03/13/2393748.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211015/9ecf6b8d42314965aeab3865983ff375.png