Module: Algoritmo di Ford-Bellman


Problem

1/6

Ford-Bellman: L'inizio (C++)

Theory Click to read/hide

Algoritmo Ford-Bellman
Diamo un grafo pesato diretto G con n vertici e m archi, e alcuni vertici iniziali v . È necessario trovare le lunghezze dei percorsi più brevi dal vertice v a tutti gli altri vertici.

Come Dijkstra, Ford-Bellman cerca la distanza dal vertice 1 a tutti gli altri, ma lavora con bordi negativi< / forte>.
 
L'algoritmo Ford-Bellman stesso consiste in diverse fasi (n-1). Ad ogni fase, vengono esaminati tutti gli archi del grafo e l'algoritmo cerca di rilassarsi lungo ogni arco (a, b) del costo c. Relax lungo un bordo — questo è un tentativo di migliorare il significato di d[a]  il valore d[b] + c. In effetti, questo significa che stiamo cercando di migliorare la risposta per il vertice utilizzando il bordo  e la risposta corrente per la parte superiore.

L'array d è un array delle lunghezze più brevi dal vertice iniziale, proprio come in Dijkstra, inizialmente lo riempiamo con i numeri più grandi possibili, ad eccezione del vertice iniziale, in cui devi inserire 0.
Per memorizzare gli spigoli non viene utilizzata una matrice di adiacenza o una matrice di peso, ma una lista che indica da quale nodo parte lo spigolo (from), a quale arriva (to) e il suo peso (cost).
  struct bordo { int da, a, costo; }; vettore<bordo> bordi;
La costante INF denota il numero "infinito" - deve essere scelto in modo tale da superare ovviamente tutte le possibili lunghezze di percorso.

L'implementazione più semplice dell'algoritmo: d[v] = 0; per (int i=0; i<n-1; ++i) for (int j=0; j<m; ++j)      if (d[edge[j].from] <INF)        d[bordi[j].to] = min(d[bordi[j].to], d[bordi[j].da] + bordi[j].cost);

o un po' più breve usando la sintassi C++11:
  d[v] = 0; per (int i=0; i< n-1; ++i) per (bordo j: bordi) if (d[j.from] <INF) d[j.to] = min(d[j.to], d[j.from] + j.cost);

Esempio di lavoro


Prendi un semplice grafico diretto  con 5 nodi, 4 spigoli con peso pari a 1.

Introduciamo un elenco di spigoli in quest'ordine.
4 5 1
3 4 1
2 3 1
1 2 1

Valori iniziali nell'array di lunghezze minime:
 
0 inf inf inf inf

dove inf dovrebbe essere un numero intero corrispondente che è sempre maggiore del peso del bordo.

Dopo il 1° passaggio
 
0 1 inf inf inf

Dopo il 2° passaggio
 
0 1 2 inf inf

Dopo il 3° passaggio
 
0 1 2 3 inf


Dopo il 4° passaggio
 
0 1 2 3 4

Se inseriamo i bordi nell'ordine dall'1 all'ultimo, potremmo trovare le lunghezze più corte dopo la prima passata.

 

Problem

Completa il programma in modo che risolva correttamente il seguente problema.

Dato un grafo orientato che può avere più spigoli e loop. Ogni spigolo ha un peso espresso come numero intero (possibilmente negativo). È garantito che non ci sono cicli di peso negativi.
Devi calcolare le lunghezze dei percorsi più brevi dal vertice numero 1 a tutti gli altri vertici.
 
Input
Il programma riceve prima il numero N (1 <= N <= 100) – il numero di vertici del grafico e il numero M (0 <= M <= 10000) – numero di costole. Le righe seguenti contengono M di triple di numeri che descrivono i bordi: l'inizio del bordo, la fine del bordo e il peso (peso – è un numero intero compreso tra -100 e 100).< /div>
 
Uscita
Il programma dovrebbe produrre N numeri – distanze dal vertice numero 1 a tutti i vertici del grafico. Se non esiste un percorso per il vertice corrispondente, stampa il numero 30000 invece della lunghezza del percorso.
 
Esempi
# Input Uscita
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 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!