Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/10/30
003// Problema do caminho minimo: algoritmo de Dijkstra (proposto por Edsger W. Dijkstra em 1956)
004
005//  Monta lista de adjacencia de um grafo, a partir de um arquivo no forma ("0 0" e' finalizador)
006//    k i                                       k=numero de vertices, i indice do no de origem
007//    v1  ad11 custo11  ad12 custo12  ... 0 0   adjacentes ao vertice 1 (indice do adj. e custo da aresta)
008//    ...
009//    vk  adk1 custok1  adk2 custok2  ... 0 0   idem para vertice k
010
011// gcc -fsanitize=address -g -o dijkstra dijkstra.c
012
013#include <stdio.h>
014#include <stdlib.h> // para 'exit(N);'
015#include <float.h>  // FLT_MAX maior float positivo
016
017#define infinito FLT_MAX // superestimador (tem que ser maior que o custo de qualquer caminho)
018#define MaxN 100         // maximo numero de nos
019
020#define LISTA 1  // Lista nos e adjacentes (para conferir o grafo)
021
022// Lista de adjacentes
023typedef struct Lista {
024  int no;        // numero do no'
025  int ind;       // indice que o no' ocupara' em Adj[]
026  float ct;      // se esta Lista corresponde ao no' <v>, entao <ct> = custo aresta (v,w), supondo w=Adj[ind]
027  struct Lista *prox;
028  } Lista;  
029
030// Lista para o caminho minimo
031typedef struct Caminho {
032  int no;  // indice do no'
033  float d; // custo do no'
034  struct Caminho *prox;
035  } Caminho;  
036
037Lista Adj[ MaxN ];  //  lista de adjacencia para cada no' (Adj[i] = lista de adj ao no' de indice i)
038Caminho C[ MaxN ];  //  vetor para caminhos minimos (C[i] = lista de nos no cam. min. desde a origem ate' no' de indice i)
039
040// Redefine o caminho de <q>, C(q), como sendo (q,p)+C(p)
041void TrocaC (Caminho *p, Caminho *q, float d) {
042  (*q).prox = p;  
043  (*q).d = (*p).d+d; // d = verificaAdjacencia((*p).no,(*q).no)  
044  }  
045
046// Teste para saber se arquivo de entrada e' coerente (detecta erros do tipo: j aparecer na lista de i, mas i NAO aparecer na de j)
047float verificaAdjacencia (int n1, int n2) { // <n2> deve ser adjacente 'a <n1>
048  Lista *V, *W;  
049  V = Adj[n1].prox; // primeiro adjacente 'a <n1>  
050  W = V;  
051  while (W != NULL) {
052    if ((*W).no == n2) return W->ct; // ou: (*W).ct;
053    W = (*W).prox; // ou: W = W->prox;    
054    }    
055  printf("\nERRO: nos nao adjacentes, (%d, %d) nao pertence 'a AG\n", n1,n2);
056  return infinito;  
057  }  
058
059void ImprimeL (int n) { // Auxiliar: imprime lista de adjacentes ao no' de indice n
060  Lista *aux;  
061  int i;
062  printf("\n Nos    | Lista de adjacencias e custos");   
063  for (i=0; i<n; i++){
064    aux = Adj[i].prox;    
065    printf("\n No' %2d |", Adj[i].no);
066    while ( aux !=NULL ){
067      printf(" (%d , %2.1f) ", (*aux).no, (*aux).ct);
068      aux = (*aux).prox;      
069      }      
070    }    
071  }  
072
073void imprimeHeap (int n, int hi[], float Hd[]) { // Auxiliar: lista vetor que dever ser um "heap"
074  int i, i_aux;
075  for (i=0; i<n; i++) {
076    i_aux = hi[i];
077    if (Hd[ i_aux ] >= infinito)
078      printf("(%d,%d: %d, +oo) ", i, i_aux, C[i_aux].no);
079    else printf("(%d,%d: %d, %3.2f) ", i, i_aux, C[i_aux].no, Hd[ i_aux ]);    
080    }    
081  printf("\n");
082  }  
083
084void imprimeC (int origem, int n) { // Auxiliar: lista caminhos
085  int i;
086  Caminho *w;  
087  printf("\nDistancias minimas ate o no [%d]", C[origem].no);
088  for (i=0; i<n; i++) {
089    printf("\n[%d] = %2.1f\n  Caminho: ", C[i].no,C[i].d);
090    w = &C[i];
091    do {    
092      printf(" [%d]", (*w).no);
093      w = (*w).prox; 
094    } while ( w != NULL );    
095    }    
096  printf("\n");
097  }  
098
099// Computa distancia no caminho apontado por lstCam - para verificar ao final...
100float DistanciaC (Caminho *lstCam) {
101   Caminho *lstCamAux = lstCam;   
102   float aux = 0;
103   while ((*lstCamAux).prox != NULL) {
104     lstCam = lstCamAux;     
105     lstCamAux = lstCamAux->prox; // ou: (*lstCamAux).prox;     
106     aux += verificaAdjacencia(lstCam->no, lstCamAux->no);     
107     }     
108   return aux;   
109   }   
110
111
112// Monta grafa a partir de arquivo com:
113// linha  0: NG IND
114// linha  1: g1  adj1_1 custo1_1  adj1_2 custo1_2 ... 0 0
115// ...
116// linha NG: gN  adjN_1 custoN_1  adjN_2 custoN_2 ... 0 0
117void MontaGrafo (int *N, int *nA, int *inicio, char *nome) {
118  FILE *arq;  
119  Lista *aux, *ant;  
120  int Ind[ (int)1.1*MaxN ]; // se no' <k> esta' em Adj[i] => Ind[k]=i
121  int i,n;
122  float ct;
123  //D int contaS = 0;  
124  *nA = 0;  
125  if ( (arq=fopen( nome,"r" )) == NULL ) {
126    printf("\nLamento, arquivo %s inexistente\n", nome);
127    exit(1);    
128    }    
129  if (LISTA) printf("\n Nos    | Lista de adjacencias e custos");
130      
131  fscanf(arq, "%d", N);
132  fscanf(arq, "%d", inicio);
133
134  for (i=0; i<*N; i++)
135    Ind[ i ] = -1; // se posteriormente Ind[k] nao ficar pos. => ERRO    
136
137  // cada linha deve terminar com:  0 0 !!!!!  
138  for (i=0; i<*N; i++) {
139    fscanf( arq, "%d ", &n); // numero do no'
140    // if ( feof(arq) ) return;  se posicionar em final de arquivo!    
141    Adj[i].no = n;  // numero do no'    
142    Adj[i].ind = i; // indice do no'    
143    if ( n > (int)1.1*MaxN ) {
144      printf("\nErro: 1.1*MaxN nao suficiente para Ind[]\n");
145      exit(1);      
146      }      
147    if (LISTA) printf("\n No' %2d |", Adj[i].no );
148
149    Ind[ n ] = i;    
150    Adj[i].prox  = NULL;    
151    ant = NULL;    
152    fscanf(arq,"%d %f", &n, &ct);
153    while ( n || ct ) { // montar adjacentes do i-esimo no'
154      aux = malloc( sizeof(Lista) );      
155      aux->no = n;      
156      aux->ct = ct;      
157      aux->prox  = ant;      
158      if (LISTA) printf(" (%d,%2.1f)", aux->no,aux->ct);
159      (*nA)++;      
160      ant = aux;      
161      fscanf(arq,"%d %f", &n, &ct);
162      //D if (contaS++>10) { printf("\nMontaGrafo: N=%d, contaS=%d\n", *N, contaS); exit(0); }      
163      }      
164    Adj[i].prox = ant;    
165    } // for (i=0; i<*N; i++)    
166  if (LISTA) printf("\n");
167  for (i=0; i<*N; i++){ // Monta campo <ind> de todas as listas <Adj[]>
168    aux = Adj[i].prox; // primeiro adjacente do i-esimo no'    
169    while (aux != NULL) {
170      n = (*aux).no;      
171      if (Ind[n]==-1) {
172        printf("\nErro: i=%d, n=%d: Ind[%d]=-1 !!\n", i, n, n);
173        exit(1);        
174        }        
175      (*aux).ind = Ind[ n ];      
176      aux = (*aux).prox;      
177      }      
178    }    
179  } // MontaGrafo  
180
181
182// ------------------------------------------------------------------------------------------------
183// Monta um "heap" a partir do ponto A[i]. Invariante: A[i+1], A[i+2],...,A[N-1] ja deve ser "heap"
184// Propriedade de "heap": chave(i) <= min{ chave(filho_esq(i)), chave(filho_dir(i))}
185
186void troca (int i, int j, int hi[]) {
187  int aux;
188  aux  = hi[i];  
189  hi[i] = hi[j];  
190  hi[j] = aux ;  
191  }  
192
193// Monta um "heap" a partir do ponto =hi[i], hi[i+1], hi[i+2],...,hi[N-1] ja deve ser Heap
194// Neste "heap" o pai tem chave MENOR que dos filhos
195void desceHeap (int i, int n, int hi[], float Hd[] ) {
196  int j, aux1; float aux2;
197  if (hi[i]<0 || hi[i]>MaxN) { printf("Erro em 'desceHeap': i=%d, hi[%d]=%d, MaxN=%d\n", i, i, hi[i], MaxN); exit(1); }
198  aux1 = hi[i]; aux2 = Hd[ hi[i] ];  
199  j = 2*i+1;  
200  while ( j<n ) {
201    if ( j+1<n )
202      if ( Hd[ hi[j+1] ] < Hd[ hi[j] ] ) j++; // "menor" filho
203    if ( Hd[ hi[j] ] < aux2 ) hi[i] = hi[j];
204    else break; // termina o laco    
205    i = j;
206    j = 2*j+1;    
207    }    
208  hi[i] = aux1;  
209  }  
210
211// Constroi o "heap" inicialmente (chave do pai menor que dos filhos)
212void MontaHeap (int n, int hi[], float Hd[]) {
213  int i;
214  for (i=n/2; i>=0; i--)
215    desceHeap(i,n,hi,Hd);    
216  }  
217// ------------------------------------------------------------------------------------------------
218
219
220// ------------------------------------------------------------------------------------------------
221// Entrada: lista de adjacencia <Lista V[]>
222// Saida  : arvore de caminhos  <Caminho MontaC[]>
223void Dijkstra (int indice, int NG, int NA) {
224  Lista *v;  
225  int i_aux; // aux. para indices {0,1,...,NG-1}
226  int hi[ MaxN ];   // Vetor de ind. para nos de cam. min. desconhecido
227  float Hd[ MaxN ]; // Vetor de distancia para nos nao prontos
228  int i, j, min;
229
230  for (i=0; i<NG; i++) {  // Preparar distancias: C[i] sera a lista do caminho do no de <indice> ate no especifico
231    C[i].no = Adj[i].no; // pegue indice do no adjacentes    
232    C[i].d  = infinito;  // arbitre que a distancia a cada no e' +oo    
233    C[i].prox  = NULL;    
234    }    
235
236  // Definir distancia para no <indice> para outro <i> como o custo de sua aresta <indice, i>  
237  C[ indice ].d = 0.0; // distancia de <indice> ate <indice> e' 0  
238  v = Adj[indice].prox; // inicio da lista de adjacencia do no <indice>  
239
240  // Constroi vetor NAO prontos - usara um Heap Hd[.], hi[.]  
241  //D1 printf("Hd, hd: ");  
242  hi[0] = indice; Hd[indice] = C[indice].d;  
243  //D1 printf("(%d,%d: %d, %3.2f) ", 0, indice, C[indice].no, Hd[indice]);  
244  j = 1;  
245  for (i=0; i<NG; i++)
246    if (i!=indice) {
247      hi[j] = i;      // indice do no      
248      Hd[i] = infinito; // C[i].d; // distancia ate <indice>      
249      //D1 printf("(%d,%d: %d, +oo) ", j, hi[j], C[hi[j]].no);      
250      j++;      
251      }      
252
253  //D1 printf("\n");  
254
255  //D2 printf("Heap: NG=%d:\n ", NG); imprimeHeap(NG, hi, Hd);  
256
257  while (NG) { // NG>0
258    min = hi[0]; // (hi,Hd) e Heap com minimo na raiz    
259    //D3 printf("\nNG=%d, %d=min=hi[%d]=%d, Hd[%d]=%3.2f\n", NG, min, 0, hi[0], hi[0], Hd[min]);    
260    //D3 printf("Heap: "); imprimeHeap(NG, hi, Hd);    
261    v = Adj[min].prox; // inicio da lista de adjacencia do no' de indice 'min' - ?caminho na lista adj. de V[min]?    
262    //D3 printf("Atualiza: ");    
263    while (v!=NULL) { // atualiza distancia min. conhecida
264      i_aux = (*v).ind;
265      if ( C[ i_aux ].d > C[min].d + (*v).ct ) {
266        //D3 if (C[ i_aux ].d >= infinito) printf("(%d: %d, +oo) ", i_aux, C[i_aux].no);        
267        //D3 else printf("(%d: %d, %3.2f) ", i_aux, C[i_aux].no, C[i_aux].d);        
268        C[ i_aux ].d = C[min].d + (*v).ct;        
269        C[ i_aux ].prox = &C[min];        
270        Hd[ i_aux ] = C[ i_aux ].d;        
271        desceHeap(i_aux, NG, hi, Hd);        
272        }        
273      //D3 printf("\n");      
274      v = (*v).prox;      
275      }      
276    hi[0] = hi[NG-1];    
277    NG--;    
278    desceHeap(0, NG, hi, Hd);    
279    }    
280  } // void Dijkstra(int indice, int NG, int NA)  
281// ------------------------------------------------------------------------------------------------
282
283
284int main (int argc, char *argv[]) {
285  int NG, NA, inicio;
286  printf("\nInicio\n");
287  if (argc<2) {
288    printf("Falta o nome do arquivo com a descricao do Grafo\n./dijkstra nome_arq_dados.txt\n");
289    return 1;    
290    }    
291
292  MontaGrafo(&NG, &NA, &inicio, argv[1]);  
293
294  //D5 printf("\nDijkstra: NG=%d, NA=%d\n", NG, NA);  
295  //D5 ImprimeL(NG);  
296
297  Dijkstra(inicio, NG, NA); // escolher como no iniciao o no' 1  
298
299  imprimeC(inicio, NG); // Imprime caminhos minimos
300
301  return 0;  
302  }