Discussion :

[facelink]

bonjour,
je veux dans un graphe, calculer le chemin le plus court, mais ce graphe a des arcs de poids négatifs, donc je voulais savoir si l'algorithme de
Bellman-Ford convenait ?
existe-t-il d'autres algorithmes qui fassent la même chose ?
est-ce qu'on pourrait m'expliquer les principales étapes de l'algorithme de BF ?

merci.

[Invité]

Bonjour,
L'algorithme de Bellman-Ford convient parfaitement, il est fait pour ça.
Dans mes souvenirs, c'est le seul car les autres comme Dijkstra par exemple ne sont possible qu'avec des poids positifs.
Pour plus d'infos sur l'algo de Bellman-Ford, il suffit d'aller sur wikipedia par exemple où il te donne l'algo (il y a une page "Algorithme de Bellman-Ford") .
Il y a aussi ce site qui te donne un exemple et le même algo (un peu plus développé) :
http://brassens.upmf-grenoble.fr/IMS...llmannFord.htm
J'espère que ça va t'aider
Bonne journée.

[facelink]

merci.
Les algorithmes comme ceux de Bellman ou Dijikstra, n'affichent comme résultat, le chemin le plus court, mais est-ce qu'il est possible d'afficher le chemin qu'il a suivi, c-à-d, comment afficher les sommets correspondants ?

[Invité]

Bonjour,
Il suffit d'ajouter dans le code un vecteur, une liste, un tableau qui garde en mémoire le chemin parcouru. Et si ensuite tu trouves un meilleur chemin, tu supprimes les éléments de ton 1er vecteur que tu remplaces par celui que tu viens de trouver.
En fait, tu aurais 2 vecteurs :

1 qui garde le meilleur chemin parcouru jusqu'à maintenant (à l'initial vide)

1 qui te permettrait de sauvegarder le chemin que tu es en train de construire

comme ça soit tu gardes ton premier vecteur, soit tu copies le chemin que tu viens de parcourir dans le 1er vecteur.

[facelink]

merci, mais comment appliquer cela dans cette fonction BF :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
 
#define INFINITY ((1 << 14)-1)
 
typedef struct {
    int source;
    int dest;
    int weight;
} Edge;
 
void BF(Edge edges[], int edgecount, int nodecount, int source)
{
    int *distance = malloc(nodecount * sizeof *distance);
    int i, j;
    for (i=0; i < nodecount; ++i)
      distance[i] = INFINITY;
    distance[source] = 0;
 
    for (i=0; i < nodecount; ++i) {
        for (j=0; j < edgecount; ++j) {
            if (distance[edges[j].source] != INFINITY) {
                int new_distance = distance[edges[j].source] + edges[j].weight;
                if (new_distance < distance[edges[j].dest])
                  distance[edges[j].dest] = new_distance;
            }
        }
    }
 
    for (i=0; i < edgecount; ++i) {
        if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
            puts("Cycles de poids de bord négatifs découverts!");
            free(distance);
            return;
        }
    }
 
    for (i=0; i < nodecount; ++i) {
        printf("La distance la plus courte entre les noeuds %d et %d est %d\n",
            source, i, distance[i]);
    }
    free(distance);
    return;
}
 
int main(void)
{
    Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
                      {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
                      {4,0, 6}, {4,2, 7}};
    BF(edges, 10, 5, 4);
    return 0;
}

cette fonction BF renvoie la distance la plus courte entre le noeud de départ et les autres noeuds, et je veux afficher le chemin qu'il a suivi qui aboutit au plus court chemin (pour chaque plus court chemin).
Le tableau distance change au fur et à mesure, donc je ne vois pas ce qu'il faut ajouter dans cette fonction pour qu'il puisse afficher le chemin ?

merci de votre aide.

[facelink]

personne ne sait ?