Alisson_Leao_Tobolsky_RAN348FB9_Algoritmo_Dijkstra

Prévia do material em texto

DIJKSTRA
Código, exemplos e atividades;
Discente: Alisson Leão Tobolsky RA: N348FB-9
Turma: CC4A28
Docente: Elio Idalgo Junior
INTRODUÇÃO 
• O Algoritmo de Dijkstra é um dos algoritmos que calcula o caminho mínimo entre 
vértices de um grafo. este algoritmo calcula o custo mínimo desta vértice para todos 
as demais vértices do grafo. Ele não garante, contudo, a exatidão da solução caso 
haja a presença de arcos com valores negativos.
• O algoritmo parte de uma estimativa inicial para o custo mínimo e ao longo do 
caminho vai sucessivamente se ajustando com esta estimativa.
• A única desvantagem são os caminhos negativos que não são capaz de calcular a 
rota negativa 
EXEMPLOS 
GPS
REDES
PERGUNTAS?
CONCEITO DIJKSTRA
1 – Qual o conceito do algoritmo Dijkstra?
R: soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido 
com arestas de peso não negativo, em tempo computacional O(m + n log n) onde m é o 
número de arestas e n é o número de vértices.
FUNCIONALIDADE DO ALGORÍTMO
2 – Sobre o algoritmo Dijkstra
I – Soluciona o problema do caminho mais curto;
II – Pode solucionar grafos com arestas negativas
III - O algoritmo de Dijkstra é um exemplo de algoritmo guloso que gera a solução ótima em tempo 
polinomial 
podemos afirmar que:
( )Apenas I está certa;
( )Apenas I e II estão certas;
(x)Apenas I e III estão Certas;
( )Todas estão certas;
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define FLSH gets(l)
int dest, orig, vertic = 0;
int custo, *custos = NULL; 
void dijkstra(int vertic,int orig,int dest,int *custos)
{
int i,v, cont = 0;
int *ant, *tmp; 
int z; / vertices para os quais se conhece o caminho minimo */
double min;
double dist[vertic]; /* vetor com os custos dos caminhos */
/* aloca as linhas da matriz */
ant = calloc (vertic, sizeof(int *));
tmp = calloc (vertic, sizeof(int *));
for (i = 0; i < vertic; i++) {
if (custos[(orig - 1) * vertic + i] !=- 1) {
ant[i] = orig - 1;
dist[i] = custos[(orig-1)*vertic+i];
}
else {
ant[i]= -1;
dist[i] = HUGE_VAL;
}
z[i]=0;
}
z[orig-1] = 1;
dist[orig-1] = 0;
/* Laco principal */
do {
/* Encontrando o vertice que deve entrar 
em z */
min = HUGE_VAL;
for (i=0;i<vertic;i++)
if (!z[i])
if (dist[i]>=0 && dist[i]<min) {
min=dist[i];v=i;
}
/* Calculando as distancias dos novos vizinhos de z */
if (min != HUGE_VAL && v != dest - 1) {
z[v] = 1;
for (i = 0; i < vertic; i++)
if (!z[i]) {
if (custos[v*vertic+i] != -1 && dist[v] + custos[v*vertic+i] < 
dist[i]) {
dist[i] = dist[v] + custos[v*vertic+i];
ant[i] =v;
}
}
}
} while (v != dest - 1 && min != HUGE_VAL);
/* Mostra o Resultado da busca */
printf("\tDe %d para %d: \t", orig, dest);
if (min == HUGE_VAL) {
printf("Nao Existe\n");
printf("\tCusto: \t- \n");
}
else {
i = dest;
i = ant[i-1];
while (i != -1) {
tmp[cont] = i+1;
cont++;
i = ant[i];
}
for (i = cont; i > 0 ; i--) {
printf("%d -> ", tmp[i-1]);
}
printf("%d", dest);
printf("\n\tCusto: %d\n",(int) dist[dest-1]);
}
}
void limpar(void)
{
}
void cabecalho(void)
{
limpar();
printf("Implementacao do Algoritmo de Dijasktra\n");
printf("Comandos:\n");
printf("\t d - Adicionar um Grafo\n"
"\t r - Procura Os Menores Caminhos no Grafo\n"
"\t CTRL+c - Sair do programa\n");
printf(">>> ");
}
void add(void)
{
int i, j;
do {
printf("\nInforme o numero de vertices (no minimo 2 ): ");
scanf("%d",&vertic);
} while (vertic < 2 );
if (!custos)
free(custos);
custos = (int *) 
malloc(sizeof(int)*vertic*vertic);
for (i = 0; i <= vertic * vertic; i++)
custos[i] = -1;
printf("Entre com as Arestas:\n");
do {
do {
printf("Origem da aresta (entre 1 e %d ou 
'0' para sair): ", vertic);
scanf("%d",&orig);
} while (orig < 0 || orig > vertic);
if (orig) {
do {
printf("Destino da aresta (entre 1 e %d, 
menos %d): ", vertic, orig);
scanf("%d", &dest);
} while (dest < 1 || dest > vertic || dest
== orig);
do {
printf("Custo (positivo) da aresta do vertice %d para o vertice %d: ",
orig, dest);
scanf("%d",&custo);
} while (custo < 0);
custos[(orig-1) * vertic + dest - 1] = custo;
}
} while (orig);
}
void procurar(void)
{
int i, j;
printf("Lista dos Menores Caminhos no Grafo Dado: \n");
for (i = 1; i <= vertic; i++) {
for (j = 1; j <= vertic; j++)
dijkstra(vertic, i,j, custos);
printf("\n");
}
printf("<Pressione ENTER para retornar ao menu principal>\n");
}
int main(int argc, char **argv) {
int i, j; 
char opcao[3], l[50]; 
do {
cabecalho();
scanf("%s", &opcao);
if ((strcmp(opcao, "d")) == 0) {
add(); 
}
FLSH;
if ((strcmp(opcao, "r") == 0) && (vertic > 0) ) {
procurar();
FLSH;
}
} while (opcao != "x"); 
printf("\nAte a proxima...\n\n");
return 0;
}