Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #define GRAPHSIZE 2048
- #define INFINITY GRAPHSIZE*GRAPHSIZE
- #define MAX(a, b) ((a > b) ? (a) : (b))
- int e; /* O número de arestas diferentes de zero no gráfico */
- int n; /* O número de nós no gráfico */
- 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 */
- long d[GRAPHSIZE]; /* d[i] é o comprimento do caminho mais curto entre a fonte e o nó i */
- int prev[GRAPHSIZE]; /* prev [i] é o nó que vem logo antes i no caminho mais curto a partir da fonte para i */
- void printD()
- {
- int i;
- printf("Distancias:\n");
- for (i = 1; i <= n; ++i)
- printf("%10d", i);
- printf("\n");
- for (i = 1; i <= n; ++i)
- {
- printf("%10ld", d[i]);
- }
- printf("\n");
- }
- /*
- Imprime o caminho mais curto a partir da fonte para dest.
- dijkstra(int) deve ser executado pelo menos uma vez antes
- esta é chamada
- */
- void printPath(int dest)
- {
- if (prev[dest] != -1)
- printPath(prev[dest]);
- printf("%d ", dest);
- }
- void dijkstra(int s)
- {
- int i, k, mini;
- int visited[GRAPHSIZE];
- for (i = 1; i <= n; ++i)
- {
- d[i] = INFINITY;
- prev[i] = -1; /* nenhum caminho foi encontrada ainda para i */
- visited[i] = 0; /* o i-ésimo elemento ainda não tenha sido visitado */
- }
- d[s] = 0;
- for (k = 1; k <= n; ++k)
- {
- mini = -1;
- for (i = 1; i <= n; ++i)
- if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
- mini = i;
- visited[mini] = 1;
- for (i = 1; i <= n; ++i)
- if (dist[mini][i])
- if (d[mini] + dist[mini][i] < d[i])
- {
- d[i] = d[mini] + dist[mini][i];
- prev[i] = mini;
- }
- }
- }
- int main(int argc, char *argv[])
- {
- int i, j;
- int u, v, w;
- int menu, m, inicio=0;
- char digitado[100], origem[10], destino[10], custo[10];
- FILE *ponteiro;
- do{
- do{
- //system("cls");
- printf("\nMenu de opcoes:\n\n");
- printf("1 - Quantidade de Arestas\n");
- printf("2 - Ler Arquivo\n");
- printf("3 - Insere as Rotas\n");
- printf("4 - Dijkstra\n");
- printf("5 - Sair\n");
- scanf("%d",&menu);
- }while((menu<1) || (menu>5));
- if(menu==1){
- system("cls");
- printf("INFORME A QUANTIDADE DE ARESTAS:\n");
- fflush(stdin);
- fgets(digitado,40, stdin);
- ponteiro = fopen("dist.txt", "wb"); // abre o arquivo para escrita no final do arquivo
- fprintf(ponteiro, "%s",digitado);
- fclose(ponteiro);
- m=0;// pra retornar ao menu
- }
- if(menu==2){
- ponteiro = fopen("dist.txt", "r");
- if(ponteiro==NULL){
- printf("Nao existe nenhum arquivo.\n\n");
- }else{
- fgets(digitado,100,ponteiro);
- fclose(ponteiro);
- system("cls");
- printf("Abertura e leitura de arquivo realizada com sucesso.\n\n %s\n", digitado);
- m=0;
- }
- }
- if(menu==3){
- ponteiro = fopen("dist.txt", "rb");
- if(ponteiro==NULL){
- printf("Nao existe nenhum arquivo.\n\n");
- }else{
- system("cls");
- FILE *fin = fopen("dist.txt", "rb");
- fscanf(fin, "%d", &e);
- for (i = 0; i < e; ++i)
- for (j = 0; j < e; ++j)
- dist[i][j] = 0;
- n = -1;
- for (i = 0; i < e; ++i){
- printf("INFORME A ORIGEM, O DESTINO E O CUSTO:\n");
- fflush(stdin);
- fgets(digitado,40, stdin);
- ponteiro = fopen("dist.txt", "ab"); // abre o arquivo para escrita no final do arquivo
- fprintf(ponteiro, "%s",digitado);
- fclose(ponteiro);
- m=0;// pra retornar ao menu
- }
- fclose(fin);
- }
- }
- if(menu==4){
- system("cls");
- FILE *fin = fopen("dist.txt", "r");
- fscanf(fin, "%d", &e);
- for (i = 0; i < e; ++i)
- for (j = 0; j < e; ++j)
- dist[i][j] = 0;
- n = -1;
- for (i = 0; i < e; ++i)
- {
- fscanf(fin, "%d%d%d", &u, &v, &w);
- dist[u][v] = w;
- n = MAX(u, MAX(v, n));
- }
- fclose(fin);
- printf("INFORME A ORIGEM:\n");
- scanf("%d", &inicio);
- dijkstra(inicio);
- printD();
- printf("\n");
- for (i = 1; i <= n; ++i)
- {
- printf("Caminho para %d: ", i);
- printPath(i);
- printf("\n");
- }
- }
- }while(menu!=5);
- return 0;
- getchar();
- getchar();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement