Jump to content

Algoritmo de Dijkstra


Localhost
 Share

Recommended Posts

Após algum tempo a procurar e a tentar entender fui resolver um problema clássico do Algoritmo de Dijkstra. Gostava de ter algum feedback sobre a minha implementação, ignorem alguns pormenores do próprio problema.

Basicamente é para determinar o caminho mais curto entre duas cidades.

#include <cstdio>
#include <queue>
#include <limits.h>
#include <cstring>

using namespace std;

typedef struct {
    int cost,dest;
}Edge;

typedef struct {
    int sum;
    bool used;
    char name[20];
    queue<Edge> edges;
}Vertex;

int s,n,p,r;
Vertex vertex[10000];

void dijkstra(int src, int dest) {
    int min=0,quant=n;
    Edge head;
    while(quant > 0) {
        min = INT_MAX;
        for(int i=0;i<n;i++) {
            if(vertex[i].used == 0) {
                if(vertex[i].sum < min) min = i;
            }
        }
        vertex[min].used = true;
        while(!vertex[min].edges.empty()) {
            head = vertex[min].edges.front();
            vertex[min].edges.pop();
            if(vertex[min].sum + head.cost < vertex[head.dest].sum) vertex[head.dest].sum = vertex[min].sum + head.cost;
        }
        quant--;
    }
    printf("%i\n",vertex[dest].sum);
}

void input() {
    Edge novo;
    char orig[20],dest[20];
    int o=0,d=0;
    scanf("%i",&n);
    for(int i=0;i<n;i++) {
        scanf("%s",vertex[i].name);
        vertex[i].sum=INT_MAX;
        vertex[i].used=false;
        scanf("%i",&p);
        for(int j=0;j<p;j++) {
            scanf("%i %i",&novo.dest,&novo.cost);
            novo.dest--;
            vertex[i].edges.push(novo);
        }
    }
    scanf("%i",&r);
    scanf("%s %s",orig,dest);
    for(int j=0;j<n;j++) if(strcmp(vertex[j].name,orig)==0) { o=j; break; }
    for(int j=0;j<n;j++) if(strcmp(vertex[j].name,dest)==0) { d=j; break; }
    vertex[o].sum = 0;
    dijkstra(o,d);
} 

int main() {
    input();
    return 0;
}

here since 2009

Link to comment
Share on other sites

        min = INT_MAX;
        for(int i=0;i<n;i++) {
            if(vertex[i].used == 0) {
                if(vertex[i].sum < min) min = i;
            }
        }
        vertex[min].used = true;

Esta parte está mal.

Hei, estás a usar uma queue e a fazer pop dos edges? Não há necessidade nenhuma, não faças isso porque destróis o grafo. Usa antes um vector.

Link to comment
Share on other sites

Podias explicar porque é que está mal, eu realmente quando estava a resolver o problema tive dificuldades em encontrar o minimo e depois lembrei-me de pôr min sempre a inf.

Ok, vou começar a usar um vector.

edit: Era muito mais fácil se eu soubesse usar a priority queue da STL, saber sei mas ela retorna sempre o elemento mais alto. 😛

here since 2009

Link to comment
Share on other sites

A priority queue não te dá jeito para substituir o vector naquele sítio. Daria jeito é para substituir a tua variável "sum" nos nós e evitar a pesquisa linear.

Para encontrar a posição do mínimo precisas de duas variáveis: uma para guardar a posição e outra o valor.

Link to comment
Share on other sites

Era precisamente isso que estava a dizer. Em vez de ter um array com os vértices tinha uma PQ.

Lol, que erro noob que fiz mesmo! Além de que não precisava de duas variáveis.. Bastava fazer:

if(vertex[i].sum < vertex[min].sum) min = i;

Certo?

Esquece o que disse. Estou a resolver um problema e já percebi o porquê das duas variáveis.

here since 2009

Link to comment
Share on other sites

No meio de tantas coisas complicadas estou a ter dificuldades no que é simples e no que se aprende nos primeiros dias de quando se está a programar. Se eu criar uma função para encontrar o minimo já não tenho problemas lol.

here since 2009

Link to comment
Share on other sites

Se queres usar só uma variável, inicializá-la a -1 e fazer esta verificação é por vezes uma alternativa.

if(min == -1 || vertex[i].sum < vertex[min].sum) min = i;

Podes sempre comparar com -1 para saber se não se encontrou nenhum.

Repara é que para poupar uma variável estás a penalizar o tempo de execução com a comparação extra, não penses que esta é uma solução melhor. É uma solução possível, só isso.

No fundo, keep it simple.

Link to comment
Share on other sites

Criei uma função e já não esses problemas. Consegui resolver mais um problema com o Algoritmo de Dijkstra.  😛

https://www.spoj.pl/problems/EZDIJKST/

#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

typedef struct {
    int cost,dest;
}Edges;

typedef struct {
    int dist;
    bool used;
    queue<Edges> edges;
}Vertex;

int n,v,k;
Vertex vertex[10000];

int find_min() {
    int minPos=0,minVal=INT_MAX;
    for(int i=0;i<k;i++) {
        if(vertex[i].used == false) {
            if(vertex[i].dist<minVal) { minVal=vertex[i].dist; minPos=i; }
        }
    }
    return minPos;
}

void dijkstra(int from, int to, int u) {
    int aux=k;
    Edges head;
    for(int i=0;i<10000;i++) { vertex[i].dist = INT_MAX; vertex[i].used = false; }
    vertex[from].dist = 0;
    while(aux>0) {
        int minPos=0;
        minPos = find_min();
        vertex[minPos].used = true;
        while(!vertex[minPos].edges.empty()) {
            head = vertex[minPos].edges.front();
            vertex[minPos].edges.pop();
            if(vertex[minPos].dist + head.cost < vertex[head.dest].dist) vertex[head.dest].dist = vertex[minPos].dist + head.cost;
        }
        aux--;
    }
    if(vertex[to].dist >= INT_MAX) printf("NO\n");
    else printf("%i\n",vertex[to].dist);
}

void input(int u) {
    Edges novo;
    int from=0,to=0;
    scanf("%i %i",&v,&k);
    for(int i=0;i<k;i++) {
        scanf("%i %i %i",&from,&novo.dest,&novo.cost);
        novo.dest--;
        vertex[from-1].edges.push(novo);
    }
    scanf("%i %i",&from,&to);
    dijkstra(from-1,to-1,u);
}

int main() {
    scanf("%i",&n);
    for(int i=0;i<n;i++) input(i);
    return 0;
}

Agora existem algumas variações de problemas em que existem coisas que podem alterar muito.

Eu já vi outro problema que é: descobrir qual é a melhor posição a colocar algo, por exemplo, de maneira a que fique à menor distância de algo.. Deve-se usar qual algoritmo? O Floyd Warshall?

edit: Esqueci-me de dizer que neste código não ignorei a dica que me deste sobre a queue e não destruir o grafo.. mas no problema, era útil destruir logo grafo para me poupar tempo..

here since 2009

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.