Dijkstra

salut a tout , il y a t'il une personne qui peut me fournirune programme en C qui consiste a utiliser LA Methode de Dijkstra  

Merci d'avance

Salut,

un truc en C qui peut ressembler (mais qui est probablement mauvais)

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char empty;
    char visited;
    int distance;
} Case;

#define MAXINT 2000

int __min(int a, int b){
    return (a<b)?a:b;
}

int distances_(Case ** c, int x, int y){
    int nombre=0;
    int i, j;
    int min=MAXINT;
    for (i=0;i<y;i++){
        for (j=0;j<x;j++){
            if (!c[i][j].visited){
                nombre++;
                if (c[i][j].distance<min){
                    min=c[i][j].distance;
                }
            }
        }
    }
    //printf("%d %d\n", min, nombre);

    for (i=0;i<y;i++){
        for (j=0;j<x;j++){
            if (c[i][j].distance==min){
                c[i][j].visited=1;
            }
        }
    }
    for (i=0;i<y-1;i++){
        for (j=0;j<x-1;j++){
            if (c[i][j].distance==min || c[i+1][j+1].distance==min){
                if (c[i+1][j].empty){
                    c[i+1][j].distance=__min(min+1, c[i+1][j].distance);
                }
                if (c[i][j+1].empty){
                    c[i][j+1].distance=__min(min+1, c[i][j+1].distance);
                }
            }
            if (c[i+1][j].distance==min || c[i][j+1].distance==min){
                if (c[i+1][j+1].empty){
                    c[i+1][j+1].distance=__min(min+1, c[i+1][j+1].distance);
                }
                if (c[i][j].empty){
                    c[i][j].distance=__min(min+1, c[i][j].distance);
                }
            }
        }
    }
    return nombre;
}

int distance(Case ** c, int x, int y){
    int max=0, r=1, i, j;
    while(r){
        r=distances_(c,x,y);
        //printf("%d\n", r);
    }
    for (i=0;i<y;i++){
        for (j=0;j<x;j++){
            if (c[i][j].distance>max){
                max=c[i][j].distance;
            }
        }
    }
    return max;
}

int main(){
    int x, y, i, j, c;
    Case ** cases;

    scanf("%d", &x);
    scanf("%d", &y);
    cases=(Case **)malloc(y*sizeof(Case *));
    for (i=0;i<y;i++){
        cases[i]=(Case *)malloc(x*sizeof(Case));
        for (j=0;j<x;j++){
            scanf("%d", &c);
            if (c==0){
                cases[i][j].empty=1;
                cases[i][j].visited=0;
                cases[i][j].distance=MAXINT;
            }else{
                cases[i][j].empty=0;
                cases[i][j].visited=0;
                cases[i][j].distance=0;
            }
            printf("%c", ((c==0)?' ':'#'));
        }
        printf("\n");
    }
    printf("result : %d\n\n", distance(cases, x, y));
    //on affiche les distances
    for (i=0;i<y;i++){
        for (j=0;j<x;j++){
            printf("%d ", cases[i][j].distance);
        }
        printf("\n");
    }
    return 0;
}



c'est une reponse a un sujet du concours fario (que j'ai faite pour m'entrainer)

tu peux t'en inspirer si tu veux... a mon avis, c'est pas trop ce que tu cherches...


In a dream, I saw me, drop dead... U was there, U cried... It was just a dream, if I die, U won't cry, maybe, U'll be happy

Mon site (articles sur la programmation et programmes)