// enviar resposta para o e-mail prof.carmino@gmail.com
// assunto:codigo-busca-em-grafo-205-SA-DIURNO
//
// 1) qual a estrutura de dados usada 
// 2) coloque o algoritmo para funcionar
// 3) desenhe o grafo proposto no problema 
// 4) Faça uma busca com o algoritmo do exercicio 001 e este. 
//     4a) Construa a sua representação grafica.
// 	   4b) O resultado é o mesmo? 
//
#include <stdio.h>
#include <string.h>
#define MAX 100
struct FL {
  char from[20]; 
  char to[20]; 
  int distance;
  char skip; 
};
struct FL flight[MAX];
int f_pos=0; 
int find_pos=0; 
int tos=0; 
int stos=0;
struct stack {
  char from[20];
  char to[20];
  int dist;
};
struct stack bt_stack[MAX];  
struct stack solution[MAX];  
void setup(void);
int route(void);
void assert_flight(char *from, char *to, int dist);
void push(char *from, char *to, int dist);
void pop(char *from, char *to, int *dist);
void isflight(char *from, char *to);
void spush(char *from, char *to, int dist);
int find(char *from, char *anywhere);
int match(char *from, char *to);
int main(void)
{
  char from[20], to[20];
  int t, d;
  setup();
  printf ("Exercicio 2 -- Atencao !!\n");
  printf("De? ");
  gets(from);
  printf("Para? ");
  gets(to);
  do {
    isflight(from, to);
    d = route();
    tos = 0; 
  } while(d!=0);
  t = 0;
  printf("A solu‡ao ¢tima ‚: \n");
  while(t<stos) {
    printf("%s para ", solution[t].from);
    d += solution[t].dist;
    t++;
  }
  printf("%s\n", to);
  printf("A distƒncia ‚ %d\n", d);
}
void setup(void)
{
  char vetor [8][12] = {"Nova York","Chicago","Denver","Toronto","Calgary","Los Angeles","Urbana","Houston"};
  assert_flight(vetor[0],vetor[1], 1000);
  assert_flight(vetor[1],vetor[2], 1000);
  assert_flight(vetor[0],vetor[3], 800);
  assert_flight(vetor[0],vetor[2], 1900);
  assert_flight(vetor[3],vetor[4], 1500);
  assert_flight(vetor[3],vetor[5], 1800);
  assert_flight(vetor[3],vetor[1], 500);
  assert_flight(vetor[2],vetor[6], 1000);
  assert_flight(vetor[2],vetor[7], 1500);
  assert_flight(vetor[7],vetor[5], 1500);
  assert_flight(vetor[2],vetor[5], 1000);
}
void assert_flight(char *from, char *to, int dist)
{
  if(f_pos<MAX) {
    strcpy(flight[f_pos].from, from);
    strcpy(flight[f_pos].to, to);
    flight[f_pos].distance = dist;
    flight[f_pos].skip = 0;
    f_pos++;
  }
  else printf("Banco de dados de v“os cheio.\n");
}
route(void)
{
  int dist, t;
  static int old_dist = 32000;
  if(!tos) return 0; 
  t = 0;
  dist = 0;
  while(t<tos) {
    dist +=bt_stack[t].dist;
    t++;
  }
  if(dist<old_dist && dist) {
    t = 0;
    old_dist = dist;
    stos = 0; 
    while(t<tos) {
      spush(bt_stack[t].from, bt_stack[t].to, bt_stack[t].dist);
      t++;
    }
  }
  return dist;
}
match(char *from, char *to)
{
  register int t;
  for(t=f_pos; t>-1; t--)
    if(!strcmp(flight[t].from, from) &&
       !strcmp(flight[t].to, to)) return flight[t].distance;
  return 0;
}
find(char *from, char *anywhere)
{
  find_pos = 0;
  while(find_pos<f_pos) {
    if(!strcmp(flight[find_pos].from, from) &&
     !flight[find_pos].skip) {
       strcpy(anywhere, flight[find_pos].to);
       flight[find_pos].skip = 1; /* torna ativo */
       return flight[find_pos].distance;
    }
    find_pos++;
  }
  return 0;
}
void isflight(char *from, char *to)
{
  int d, dist;
  char anywhere[20];
  if(d=match(from, to)) {
    push(from, to, d);
    return;
  }
  if(dist=find(from, anywhere)) {
    push(from, to, dist);
    isflight(anywhere, to);
  }
  else if(tos>0) {
    pop(from, to, &dist);
    isflight(from, to);
  }
}
void push(char *from, char *to, int dist)
{
  if(tos<MAX) {
    strcpy(bt_stack[tos].from, from);
    strcpy(bt_stack[tos].to, to);
    bt_stack[tos].dist = dist;
    tos++;
  }
  else printf("Pilha cheia\n");
}
void pop(char *from, char *to, int *dist)
{
  if(tos>0) {
    tos--;
    strcpy(from, bt_stack[tos].from);
    strcpy(to, bt_stack[tos].to);
    *dist = bt_stack[tos].dist;
  }
  else printf("Pilha vazia\n");
}
void spush(char *from, char *to, int dist)
{
  if(stos<MAX) {
    strcpy(solution[stos].from, from);
    strcpy(solution[stos].to, to);
    solution[stos].dist = dist;
    stos++;
  }
  else printf("Pilha de menor distƒncia cheia.\n");
}

Comentários