Implementazione dell'algoritmo Bellman-Ford C++

Question

Attualmente sto lavorando a un compito a casa per implementare l'algoritmo Bellman-Ford. Finora, sono riuscito a leggere nel grafico fornito, metterlo in un vettore (usando un vettore 1d per rappresentare un 2d uno con ordine di riga maggiore) da usare come matrice. Sto usando una struttura che tiene traccia del peso del bordo, un valore booleano per indicare se è infinito (nessun fronte esiste) e una variabile per tenere traccia del nodo precedente.

Ciò di cui sono perplesso è in realtà l'implementazione dell'algoritmo dang. Ho letto lo pseudocodice da http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm ma ho difficoltà a capire come utilizzare l'algoritmo. Le prime 80 righe stanno leggendo nel file, inizializzando il vettore, gettando i valori nel vettore nel posto giusto. Di seguito è quello che ho iniziato ad implementare per l'algoritmo. Ho alcune domande specifiche.

1) In tutte le spiegazioni dell'algoritmo che ho trovato, si lavora l'algoritmo # di nodi - 1 volta. In alcune delle implementazioni che ho visto, sono tendenzialmente iniziato a 1. Perché è questo? Inoltre, con la mia implementazione, ha ancora senso?

2) Più avanti nello pseudocodice di wikipedia, si dice di verificare ogni spigolo u, v, essendo il vertice di partenza u e il vertice di fine v. Nella mia matrice, per quanto posso capire, vorremmo dire che devo controllare il peso/valore di ogni riga, la coppia di colonne e vedere se c'è un percorso migliore. Non sono ... sicuro se lo sto spiegando correttamente o addirittura lo capisco come questo punto. Qualsiasi consiglio/guida/suggerimento/dimostrazione sarebbe molto apprezzato. Il codice sorgente seguito da una copia dell'ingresso dimostrativo dell'istruttore è riportato di seguito.

#include <fstream> 
#include <iostream> 
#include <iomanip> 
#include <vector> 

using namespace std; 

struct graphNode 
{ 
    int value; //Weight of the edge 
    bool isInfinity; //Boolean to flag an edge as infinity 
    int pred; //predecessor node 
}; 

// Code for reading inputfile cribbed and modified from http://stackoverflow.com/questions/7651243/c-read-a-file-name-from-the-command-line-and-utilize-it-in-my-file 
int main(int argc, char** argv) 
{ 
    ifstream input; // ifstream for the input 
    string inFile = ""; //name of the input file 
    int row; //Variable to keep track of what row we're inputting data for 
    int col; //Variable to keep track of a column thingie, expand on this later 
    int infinity = 99999999; 
    int nodeCount; //Number of nodes from input file 
    int edgeCount = 0; //Number of edges from the input file 

    vector<graphNode> edgeList; //2D list of edges, order is a->b 
    edgeList.push_back(graphNode()); 
    edgeList[0].value = 0; 
    edgeList[0].isInfinity = false; 
    edgeList[0].pred = -1; 

    if(argc == 2) 
    { 
     inFile = argv[1]; 
    } 
    else 
    { 
     cout << "Usage: ./a.out inputFile\n"; 
     return 1; 
    } 

    input.open(inFile.c_str()); // opening the provided file 

    if(input.is_open()) // making sure the input is open 
    { 
     input >> nodeCount; //Grabbing the number of nodes from the first value of the file 

     for(int i = 1; i < nodeCount*nodeCount; i++) 
     { 
      edgeList.push_back(graphNode()); 
      edgeList[i].value = infinity; 
      edgeList[i].isInfinity = true; 
      edgeList[i].pred = -1; 
     } 

     //Putting data from the file into the vector array 
     while(!input.eof()) 
     { 
      input >> row; //For each cycle through the list, we grab the first number on the line to get which x value (start vertex) we're working with 
      while(input.peek() != '\n' && input.peek() != '\r' && !input.eof()) 
      { 
       input >> col; 
       input >> edgeList[((row-1)*nodeCount)+(col-1)].value; 
       edgeList[((row-1)*nodeCount)+(col-1)].isInfinity = false; 
       edgeList[((row-1)*nodeCount)+(col-1)].pred = row; 
       edgeCount++; 
      } 

     } 
     input.close(); //Closing our input file since we don't need it anymore 
    } 
    else 
    { 
     cout << "Error, something happened with the input." << endl; 
     return 1; 
    } 

    //for(int i = 0; i < nodeCount - 1; i++) 
    //{ 
     //for(int r = 0; r < nodeCount - 1; r++) 
     //{ 
      //for(int c = 0; r < nodeCount - 1; c++) 
      //{ 
       //if(r == c) continue; 
       //if(edgeList[r][c].isInfinity) continue; 
       //if(edgeList[i][r] + edgeList[r][c] < edgeList[c][i]) 
} 

ingresso Demo:

10 
3 6 4 9 0 7 8 
8 5 3 7 3 4 -2 
5 10 2 8 1 4 1 
2 6 -3 1 3 7 1 
1 10 -1 2 2 4 -2 
10 9 -3 1 3 7 2 5 1 
7 3 0 10 1 2 1 8 2 
9 6 6 3 4 10 7 
4 8 5 1 9 5 6 
6 2 4 3 0 9 0 

Answer 1

per # 1, si sta esaminando i bordi tra i nodi in modo tale che il percorso più lungo non può essere superiore a nodeCount-1 spigoli. Ad esempio, se nodeCount == 1, non è necessario esaminare alcun bordo.

Per # 2, si dispone di strutture dati interessanti. Sembra che tu abbia bisogno di diversi. Il tuo 'graphNode' dovrebbe essere chiamato 'graphEdge' ma senza la variabile 'pred'. Dichiarare due nuove strutture:

vector<int> predecessor; 
vector<int> distance; 

Ogni è di dimensione nodoCunto. La "w" che vedi in Wikipedia è la tua lista dei margini.

Nell'ultima sezione che avete commentato, il ciclo esterno sta iterando le volte nodoConteggio. Dovrebbe essere nodeCount-1, ma nessun danno. La tua indicizzazione in seguito è disattivata, tuttavia, dal momento che hai una lista di dimensioni unidimensionale che stai trattando come bidimensionale. È possibile accedere al bordo corretto tramite edgeList [(r-1) * nodeCount + c].

Non sicuro se questo conta come una risposta, ma è un inizio.

Answer 2

Guarda qui i brevi video sull'algoritmo di Bellman-Ford. Penso che possa aiutare a capire l'algoritmo migliore: https://class.coursera.org/algo2-2012-001/lecture/preview

Fondamentalmente l'idea principale dietro Bellman-Ford è questo:

Per trovare un percorso più breve tra 2 nodi, dicono s e t, è iterativamente trovare il percorso più breve per ottenere da s a t, e in ogni iterazione successiva, consentire all'algoritmo di utilizzare 1 altro margine nel percorso rispetto alla precedente iterazione.

In qualsiasi particolare k iterazione, dove ora consente all'algoritmo di utilizzare al massimo k bordi in un percorso, il percorso più breve tra s e t potrebbe o

1. migliorare utilizzando esattamente k i bordi o
2. prendono lo stesso valore di quello trovato dall'iterazione precedente, ad esempio usea al massimo (k - 1) bordi.

Così, in una particolare iterazione k:

Let d [k] [t] sia la distanza da s ad un nodo mediante t al massimo k archi. Poi:

d[ k ][ t ] = min{ 
d[k - 1][ t ], # Case 2 
for all edges (u, t) in graph min d[k - 1][ u ] + c[ u ][ t ] # Case 1 
} 

cui la seconda parte del min {..,} Suddetta equazione semplicemente trova il percorso più breve tra s a qualsiasi vicino u della destinazione finale t e aggiungere il costo del bordo c [u] [t] per passare da u a t, richiedendo in tal modo esattamente k bordi.

Il pseudocodice sembra così simile a questo:

d[s][0] = 0 # The cost from s to itself requiring zero edges is 0. 
d[u][0] = INFINITY for all other nodes other than s (i.e. you cannot reach them with no edges). 

Let n = number of nodes in graph 
for k = 1 to n - 1: # Allow one more edge in path in each iteration 
    for every edge (u, v) in edges of graph: # Check whether can get a better cost to v using k edges by going through node u or k - 1 edges is enough. 
    d[ v ][ k ] = min{ d[k - 1][ v ], d[k - 1][ u ] + c[ u ][ v ] } 

Per rispondere a parte 1 della tua domanda, si consideri che il ciclo esterno dell'equazione passanti sopra il numero di spigoli. Aumenta da 1 a n - 1, dove n è il numero di nodi nel grafico. Il motivo per cui è fino a n - 1 è che il numero massimo di archi che si possono avere in un percorso sono i bordi (n - 1) (cioè si finisce per connettere tutti i nodi per ottenere da s a t, con n - 1 spigoli fra loro).

Per rispondere alla parte 2 della domanda, è necessario considerare solo i nodi in arrivo per ogni nodo di destinazione e verificare se un percorso verso uno di quei nodi utilizza bordi k-1 PIÙ il costo da tale nodo al costo del nodo di destinazione meno di prima, come ho spiegato sopra.

Infine, per controllare il ciclo negativo (l'ultima parte nel codice wiki), si esegue l'algoritmo per 1 altra iterazione. Sappiamo che qualsiasi percorso può utilizzare al massimo n - 1 spigoli. Qualsiasi altro sarebbe ridondante. Quindi, se il costo di qualsiasi percorso diminuisce quando si consente di usare 1 più spigoli, deve aver incluso un ciclo negativo perché questo è l'unico modo in cui il suo costo potrebbe essere diminuito. Qualsiasi ciclo non negativo avrebbe comportato lo stesso costo o maggiore di quello utilizzato più bordi.

Consiglio vivamente di guardare il video di Tim Roughgarden nel link sopra. Si noti che il suo trattamento è leggermente diverso dallo pseudocodice in wikipedia, ma l'idea è essenzialmente la stessa.