Advertisement
leors

Grafo Dijkstra salvando em Arquivo

Jun 17th, 2015
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.29 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #define GRAPHSIZE 2048
  5. #define INFINITY GRAPHSIZE*GRAPHSIZE
  6. #define MAX(a, b) ((a > b) ? (a) : (b))
  7.  
  8. int e; /* O número de arestas diferentes de zero no gráfico */
  9. int n; /* O número de nós no gráfico */
  10. long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] é a distância entre o nó i e j; ou 0 se não há nenhuma conexão direta */
  11. long d[GRAPHSIZE]; /* d[i] é o comprimento do caminho mais curto entre a fonte e o nó i */
  12. int prev[GRAPHSIZE]; /* prev [i] é o nó que vem logo antes i no caminho mais curto a partir da fonte para i */
  13.  
  14. void printD()
  15. {
  16.     int i;
  17.  
  18.     printf("Distancias:\n");
  19.     for (i = 1; i <= n; ++i)
  20.         printf("%10d", i);
  21.     printf("\n");
  22.     for (i = 1; i <= n; ++i)
  23.     {
  24.         printf("%10ld", d[i]);
  25.     }
  26.     printf("\n");
  27. }
  28.  
  29. /*
  30. Imprime o caminho mais curto a partir da fonte para dest.
  31. dijkstra(int) deve ser executado pelo menos uma vez antes
  32. esta é chamada
  33.  */
  34. void printPath(int dest)
  35. {
  36.     if (prev[dest] != -1)
  37.         printPath(prev[dest]);
  38.     printf("%d ", dest);
  39. }
  40.  
  41. void dijkstra(int s)
  42. {
  43.     int i, k, mini;
  44.     int visited[GRAPHSIZE];
  45.  
  46.     for (i = 1; i <= n; ++i)
  47.     {
  48.         d[i] = INFINITY;
  49.         prev[i] = -1; /* nenhum caminho foi encontrada ainda para i */
  50.         visited[i] = 0; /* o i-ésimo elemento ainda não tenha sido visitado */
  51.     }
  52.  
  53.     d[s] = 0;
  54.  
  55.     for (k = 1; k <= n; ++k)
  56.     {
  57.         mini = -1;
  58.         for (i = 1; i <= n; ++i)
  59.             if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
  60.                 mini = i;
  61.  
  62.         visited[mini] = 1;
  63.  
  64.         for (i = 1; i <= n; ++i)
  65.             if (dist[mini][i])
  66.                 if (d[mini] + dist[mini][i] < d[i])
  67.                 {
  68.                     d[i] = d[mini] + dist[mini][i];
  69.                     prev[i] = mini;
  70.                 }
  71.     }
  72. }
  73.  
  74. int main(int argc, char *argv[])
  75. {
  76.     int i, j;
  77.     int u, v, w;
  78.    
  79.     int menu, m, inicio=0;
  80.     char digitado[100], origem[10], destino[10], custo[10];
  81.     FILE *ponteiro;
  82.  
  83.     do{
  84.         do{
  85.             //system("cls");
  86.             printf("\nMenu de opcoes:\n\n");
  87.             printf("1 - Quantidade de Arestas\n");
  88.             printf("2 - Ler Arquivo\n");
  89.             printf("3 - Insere as Rotas\n");
  90.             printf("4 - Dijkstra\n");
  91.             printf("5 - Sair\n");
  92.             scanf("%d",&menu);
  93.         }while((menu<1) || (menu>5));
  94.         if(menu==1){
  95.             system("cls");
  96.             printf("INFORME A QUANTIDADE DE ARESTAS:\n");
  97.             fflush(stdin);
  98.             fgets(digitado,40, stdin);
  99.             ponteiro = fopen("dist.txt", "wb"); // abre o arquivo para escrita no final do arquivo
  100.             fprintf(ponteiro, "%s",digitado);
  101.             fclose(ponteiro);
  102.             m=0;// pra retornar ao menu
  103.         }
  104.         if(menu==2){
  105.             ponteiro = fopen("dist.txt", "r");
  106.             if(ponteiro==NULL){
  107.                 printf("Nao existe nenhum arquivo.\n\n");
  108.             }else{
  109.                 fgets(digitado,100,ponteiro);
  110.                 fclose(ponteiro);
  111.                 system("cls");
  112.                 printf("Abertura e leitura de arquivo realizada com sucesso.\n\n %s\n", digitado);
  113.                 m=0;
  114.             }
  115.         }
  116.         if(menu==3){
  117.             ponteiro = fopen("dist.txt", "rb");
  118.             if(ponteiro==NULL){
  119.                 printf("Nao existe nenhum arquivo.\n\n");
  120.             }else{
  121.                 system("cls");
  122.                 FILE *fin = fopen("dist.txt", "rb");
  123.                 fscanf(fin, "%d", &e);
  124.                 for (i = 0; i < e; ++i)
  125.                     for (j = 0; j < e; ++j)
  126.                         dist[i][j] = 0;
  127.                 n = -1;
  128.                 for (i = 0; i < e; ++i){
  129.                     printf("INFORME A ORIGEM, O DESTINO E O CUSTO:\n");
  130.                     fflush(stdin);
  131.                     fgets(digitado,40, stdin);
  132.                     ponteiro = fopen("dist.txt", "ab"); // abre o arquivo para escrita no final do arquivo
  133.                     fprintf(ponteiro, "%s",digitado);
  134.                     fclose(ponteiro);
  135.                     m=0;// pra retornar ao menu
  136.                 }
  137.                 fclose(fin);
  138.             }
  139.         }
  140.         if(menu==4){
  141.             system("cls");
  142.             FILE *fin = fopen("dist.txt", "r");
  143.             fscanf(fin, "%d", &e);
  144.             for (i = 0; i < e; ++i)
  145.                 for (j = 0; j < e; ++j)
  146.                     dist[i][j] = 0;
  147.             n = -1;
  148.             for (i = 0; i < e; ++i)
  149.             {
  150.                 fscanf(fin, "%d%d%d", &u, &v, &w);
  151.                 dist[u][v] = w;
  152.                 n = MAX(u, MAX(v, n));
  153.             }
  154.             fclose(fin);
  155.  
  156.             printf("INFORME A ORIGEM:\n");
  157.             scanf("%d", &inicio);
  158.             dijkstra(inicio);
  159.  
  160.             printD();
  161.  
  162.             printf("\n");
  163.             for (i = 1; i <= n; ++i)
  164.             {
  165.                 printf("Caminho para %d: ", i);
  166.                 printPath(i);
  167.                 printf("\n");
  168.             }
  169.         }
  170.     }while(menu!=5);
  171.     return 0;
  172.     getchar();
  173.     getchar();
  174.     return 0;
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement