channel_problem.txt

管道问题 优化理论 动态规划?艿牢侍?优化理论 动态规划?艿牢侍?优化理论 动态规划?艿牢侍?优化理论 动态规划?艿牢侍?优化理论 动态规划?艿牢侍?优化理论 动态规划?艿牢侍?优化理论 动态规划

Prim算法，以前的代码：   
    
  void   prim(Graph   G,int   vcount,int   father[])   
  {   
        int   i,j,k;   
        int   lowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes];   
        for   (i=0;i<vcount;i++)   
              {   
                    lowcost[i]=G[0][i];   
                    closeset[i]=0;           
                    used[i]=0;                   
                    father[i]=-1;               
                    }   
        used[0]=1;                             
        for   (i=1;i<vcount;i++)   
              {   
                    j=0;   
                    while   (used[j])   j++;   
                    for   (k=0;k<vcount;k++)   
                          if   ((!used[k])&&(lowcost[k]<lowcost[j]))   j=k;     
                    father[j]=closeset[j];   
                    used[j]=1;                                 
                    for   (k=0;k<vcount;k++)   
                          if   (!used[k]&&(G[j][k]<lowcost[k]))   
                                {     lowcost[k]=G[j][k];   
                                      closeset[k]=j;     }   
                    }   
        }










Prim算法：   
            
  template<class   Type>   
  void   Prim(int   n,Type   **c)   
  {     
          Type   lowcost[maxint];   
          int   closest[maxint];   
          bool   s[maxint];   
    
          s[1]=ture;   
          for(int   i=2;i<=n;i++){   
                  lowcost[i]=c[1][i];   
                  closest[i]=1;   
                  s[i]=false;   
              }   
          for(int   i=1;i<n;i++){   
                  Type   min=inf;   
                  int   j=1;   
                  for(int   k=2;k<=n;k++)   
                          if((lowcost[k]<min)&&(!s[k])){   
                                  min=lowcost[k];   
                                  j=k;   
                              }   
                  cout<<j<<''<<closest[j]<<endl;   
                  s[j]=ture;   
                  for(int   k=2;k<=n;k++)         
                          if((c[j][k]<lowcost[k])&&(!s[k])){   
                                  lowcost[k]=c[j][k];   
                                  closest[k]=j;   
                              }   
                }   
  }   













#define   Max   999   
  #define   VertexNum     4   
  #define   EdgeNum         5   
    
  int   Graph[VertexNum][VertexNum];   
  int   Edge[EdgeNum][3]={   {   1,2,2   },{   1,3,3   },{1,4,7},{2,4,1},{3,4,2}   };   
  int   Visited[VertexNum];   
  int   Distance[VertexNum];   
    
  void   Dijkstra(int   Begin)   
  {   
    int   MinEdge;   
    int   Vertex;   
    int   i,j;   
    int   Edges;   
    
    Edges=1;   
    Visited[Begin]=1;   
    
    for(i=1;i<VertexNum;i++)   
          Distance[i]=Graph[Begin][i];   
    
    Distance[Begin]=0;   
    printf("Vertice");   
    for(i=0;i<VertexNum;i++)   
      printf("%5d",i);   
    printf("\n");   
    printf("Step   %d:",Edges);   
    for(i=0;i<VertexNum;i++)   
      printf("%5d",Distance[i]);   
    printf("\n");   
    while(Edges<(VertexNum-1))   
    {   
      Edges++;   
      MinEdge=Max;   
      for(j=0;j<VertexNum;j++)   
      {   
        if(Visited[j]==0&&MinEdge>Distance[j])   
        {   
          Vertex=j;   
          MinEdge=Distance[j];   
        }   
    }   
    Visited[Vertex]=1;   
    printf("Step   %d:",Edges);   
    for(j=0;j<VertexNum;j++)   
    {   
        if(Visited[j]==0&&Distance[Vertex]+Graph[Vertex][j]<Distance[j])   
        {   
          Distance[j]=Distance[Vertex]+Graph[Vertex][j];   
        }   
        printf("%5d",Distance[j]);   
    }   
    printf("\n");   
    }   
  }   
    
  void   Print_M_Graph()   
  {   
      int   i,j;   
      printf("Vertice");   
      for(i=1;i<VertexNum;i++)   
      {   
            printf("\n");   
        for(j=1;j<VertexNum;j++)   
            printf("%5d",Graph[i][j]);   
        printf("\n");   
      }   
  }   
    
  void   Create_M_Graph(int   Vertice1,int   Vertice2,int   Weight)   
  {   
    Graph[Vertice1][Vertice2]=Weight;   
  }   
    
  void   main()   
  {   
    int   BeginVertex=1;   
    int   i,j;   
    
    for(i=0;i<VertexNum;i++)   
      Visited[i]=0;   
    
    for(i=0;i<VertexNum;i++)   
      for(j=0;j<VertexNum;j++)   
        Graph[i][j]=Max;   
    
    for(i=0;i<EdgeNum;i++)   
      Create_M_Graph(Edge[i][0],Edge[i][1],Edge[i][2]);   
    
    printf("##Graph##\n");   
    Print_M_Graph();   
    
    printf("Dijkstra   Algorthm   :\n");   
    Dijkstra(BeginVertex);   
  }   
                  2     
          1----->2   
          |\           |   
          |   \         |     
        3|     \7     |1   
          |       \     |   
        V         \   v     
          3----->4   
                2   
  1到2的权为2，2到4的为1，1到3的为3，3到4的为2，1到4的为7，   
  由图可知最短的路径为3。