bellman_ford.cpp

bellmanford算法

#include <cstdio>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cmath>
#include <ctime>
#include <bitset>
#include <stdlib.h>
#include <stddef.h>
#include <float.h>


#define input "Bellman_Ford.in"      //Input file name
#define output "Bellman_Ford.out"    //Output file name
#define infinity 1000000      // a big int
#define max_vertexes 10000           // the max count of vertexes
using namespace std;
typedef int Graph[max_vertexes][max_vertexes];   //use adjacent matrix to represent graph

FILE *fin,*fout;
int probN,n,s,t=0;
Graph A;

int read_case()
{
   int i,j,k,m,tmp;
   if (feof(fin)) return 0;
   fscanf(fin,"%d %d",&n,&m);
   if (n==0) return 0;
   probN++;
   fscanf(fin,"%d %d",&s,&t);
   s--;t--;
   for (i=0;i<n;i++)
      for (j=0;j<n;j++)
         A[i][j]=infinity;
   printf("Graph %d:\n",probN);
   fprintf(fout,"Grahp %d:\n",probN);
   for (k=0;k<m;k++)
   { fscanf(fin,"%d %d %d",&i,&j,&tmp);
     fprintf(fout,"V(%d)-V(%d):%d\n",i,j,tmp);
     printf("V(%d)-V(%d):%d\n",i,j,tmp);
     A[i-1][j-1]=tmp;
    }
   return 1;
}

int rand_num(int no[],int NUM )
{
    int cont[NUM];
    int index, i;
    for (i=0; i<NUM; i++)
    cont[i] = i;
    srand((int)time(0));
    for (i=0; i<NUM; i++) {
        index = (int)((float)(NUM-i) * rand() / (RAND_MAX+1.0));
        no[i]=cont[index];
        cont[index] = cont[NUM-1-i];
    }
}
int input_main()
{
    int pr,su,m=0;
    div_t tmp;
    printf("Entrez le nombre de sommets: ");
    cin>>n;
    printf("Entrez le nombre d'arcs: ");
    cin>>m;
    fprintf(fout,"Aleatoire......:\nNombre de sommets:%d\n",n);
    printf("Aleatoire......:\nNombre de sommets:%d\n",n);
    fprintf(fout,"Nombre d'arcs:%d\n",m);    
    printf("Nombre d'arcs:%d\n",m);
    s=0;t=n-1;
    int no1[m],no2[n];
    for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
         A[i][j]=infinity;
    rand_num(no1,m);
    rand_num(no2,n);
    srand((int)time(0));
    for (int k=0;k<m;k++)
    {
        tmp=div(no1[k],n);
        pr=int(tmp.rem);
        tmp=div((no2[k]+pr),n);
        su=int(tmp.rem);
        A[pr][su]=1 + (int)((float)100 * rand() / (RAND_MAX + 1.0));
        fprintf(fout,"V(%d)-V(%d):%d\n",pr,su,A[pr][su]);
    }
}    

int d[max_vertexes],path[max_vertexes];

int Bellman_Ford(int success)
{
   int i,j,k;
   for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}
   d[s]=0;
   for (k=1;k<n;k++)
    for (i=0;i<n;i++)
     for (j=0;j<n;j++)
       if (d[j]>d[i]+A[i][j]) {d[j]=d[i]+A[i][j];path[j]=i;}
   success=0;
   for (i=0;i<n;i++)
    for (j=0;j<n;j++)
     if (d[j]>d[i]+A[i][j]) return 0;
   success=1;
   return 1;
 }

void print()
{
     fprintf(fout,"-----------------------------------------------------------\n");
     fprintf(fout,"Le plus court chemin entre la source et le sommet courant:\n");
     fprintf(fout,"-----------------------------------------------------------\n");
     printf("-----------------------------------------------------------\n");
     printf("Le plus court chemin entre la source et le sommet courant:\n");
     printf("-----------------------------------------------------------\n");
     for (int j=1;j<n;j++)
     {   
         int i=j;      
         while (i!=s)
               {
                     fprintf(fout,"%d<--",i+1);
                     printf("%d<--",i+1);
                     i=path[i];
               }
         fprintf(fout,"%d:%d\n",s+1,d[j]);
         printf("%d:%d\n",s+1,d[j]);
     }
}  


void solve_case()
{
    int i,success;
    time_t start,end;
    start=clock();
    Bellman_Ford(success);
    end=clock();
    if (!success) {fprintf(fout,"Non plus court chemin!\n");printf("Non plus court chemin!\n");return;}
    print();
    fprintf(fout,"Le plus court chemin :");
    printf("Le plus court chemin :");
    i=t;
    while (i!=s)
    {
    fprintf(fout,"%d<--",i+1);
    printf("%d<--",i+1);
    i=path[i];
    }
    fprintf(fout,"%d\n",s+1);
    printf("%d\n",s+1);
    fprintf(fout,"Le temps d'execution:%f\n\n",difftime(end,start));
    printf("Le temps d'execution:%f\n\n",difftime(end,start));
}

void solve_case_input()
{
    int i,success;
    time_t start,end;
    start=clock();
    Bellman_Ford(success);
    end=clock();
    fprintf(fout,"-----------------------------------------------------------\n");
    fprintf(fout,"Le plus court chemin entre la source et le sommet courant:\n");
    fprintf(fout,"-----------------------------------------------------------\n");
    for (int j=1;j<n;j++)
    {   
        int i=j;      
        while (i!=s)
              {
                    fprintf(fout,"%d<--",i+1);
                    i=path[i];
              }
        fprintf(fout,"%d:%d\n",s+1,d[j]);
    }
    fprintf(fout,"Le plus court chemin :\n");
    printf("Le plus court chemin :\n");
    i=t;
    while (i!=s)
    {
    fprintf(fout,"%d<--",i+1);
    printf("%d<--",i+1);
    i=path[i];
    }
    fprintf(fout,"%d\n",s+1);
    printf("%d\n",s+1);
    fprintf(fout,"Le temps d'execution:%f ms\n",difftime(end,start)/1000);
    printf("Le temps d'execution:%f ms\n",difftime(end,start)/1000);
}


int main()
{
   char ch;
   while (1)
   {
   printf("\n1.Démonstration avec les paramètres importé ;\n2.Entrez les parametres à la main ;\n");
   printf("Quel choix vous désirez :");
   cin>>&ch;
    switch(ch)
    {
             case '1':
                  assert(fin=fopen(input,"r"));
                  assert(fout=fopen(output,"w"));   
                  while (read_case()) solve_case();
                  fclose(fin);
                  fclose(fout);
                  break;
                   
             case '2':
                  assert(fin=fopen(input,"r"));
                  assert(fout=fopen(output,"w"));  
                  input_main();
                  solve_case_input();
                  fclose(fin);
                  fclose(fout); 
                  break;
                  
             default:
                  printf("Input erreur\n");
                  break;
    } 
   }
}