Module: Algorithme de Ford-Bellman


Problem

1/6

Ford-Bellman : Le début (C++)

Theory Click to read/hide

Algorithme de Ford-Bellman
Donnons un graphe orienté pondéré G avec n sommets et m arêtes, et quelques sommets de départ v > . Il est nécessaire de trouver les longueurs des chemins les plus courts du sommet v à tous les autres sommets.

Comme Dijkstra, Ford-Bellman recherche la distance entre le sommet 1 et tous les autres, mais fonctionne avec des arêtes négatives.
  ;
L'algorithme Ford-Bellman lui-même se compose de plusieurs phases (n-1). A chaque phase, toutes les arêtes du graphe sont examinées, et l'algorithme essaie de relaxer le long de chaque arête (a, b) du coût c. Détente le long d'un bord — ceci est une tentative d'améliorer la signification de d[a]  la valeur d[b] + c. En fait, cela signifie que nous essayons d'améliorer la réponse pour le sommet en utilisant l'arête  et la réponse actuelle pour le haut.

Le tableau d est un tableau des longueurs les plus courtes à partir du sommet de départ, tout comme dans Dijkstra, nous le remplissons initialement avec le plus grand nombre possible, sauf pour le sommet de départ, dans lequel vous devez mettre 0.
Pour stocker les arêtes, ce n'est pas une matrice d'adjacence ou une matrice de poids qui est utilisée, mais une liste qui indique de quel nœud part l'arête (from), vers laquelle elle vient (to) et son poids (coût).
  bord de la structure { int de, à, coût ; } ; vecteur<bord> bords;
La constante INF dénote le nombre "infini" - il doit être choisi de telle sorte qu'il dépasse évidemment toutes les longueurs de chemin possibles.

L'implémentation la plus simple de l'algorithme : d[v] = 0 ; pour (int i=0; i<n-1; ++i) pour (int j=0; j<m; ++j)      si (d[bords[j].de] <INF)        d[bords[j].to] = min(d[bords[j].to], d[bords[j].from] + bords[j].cost);

ou un peu plus court en utilisant la syntaxe C++11 :
  d[v] = 0 ; pour (int i=0 ; i< n-1 ; ++i) pour (arête j : arêtes) si (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

Exemple de travail


Prenez un graphe orienté simple  à 5 nœuds, 4 arêtes de poids égal à 1.

Introduisons une liste d'arêtes dans cet ordre.
4 5 1
3 4 1
2 3 1
1 2 1

Valeurs initiales dans le tableau des longueurs les plus courtes :
 
0 info info info info

où inf doit être un entier apparié qui est toujours supérieur au poids de l'arête.

Après le 1er passage
 
0 1 info info info

Après le 2e passage
 
0 1 2 info info

Après le 3ème passage
 
0 1 2 3 info


Après le 4ème passage
 
0 1 2 3 4

Si nous alimentions les arêtes dans l'ordre de 1 à la dernière, nous pourrions trouver les longueurs les plus courtes après la 1ère passe.

 

Problem

Complétez le programme afin qu'il résolve correctement le problème suivant.

Étant donné un graphe orienté qui peut avoir plusieurs arêtes et boucles. Chaque arête a un poids exprimé sous forme d'entier (éventuellement négatif). Il est garanti qu'il n'y a pas de cycles de poids négatifs.
Vous devez calculer les longueurs des chemins les plus courts du sommet numéro 1 à tous les autres sommets.
 
Entrée
Le programme reçoit d'abord le nombre N (1 <= N <= 100) – le nombre de sommets du graphe et le nombre M (0 <= M <= 10000) – nombre de côtes. Les lignes suivantes contiennent M de triplets de nombres décrivant les arêtes : le début de l'arête, la fin de l'arête et le poids (le poids – est un entier compris entre -100 et 100).< /div>
 
Sortie
Le programme devrait afficher des nombres N – distances du sommet numéro 1 à tous les sommets du graphe. S'il n'y a pas de chemin vers le sommet correspondant, imprimez le nombre 30000 au lieu de la longueur du chemin.
 
Exemples
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
# Entrée Sortie
1 0 10 20 30000 30000 30000 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
        edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {         
    }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!