Implementieren Bellman-Ford-Algorithmus C++

Question

Ich arbeite derzeit an einer Hausaufgabe, um den Bellman-Ford-Algorithmus zu implementieren. Bis jetzt habe ich es geschafft, das bereitgestellte Diagramm zu lesen, es in einen Vektor zu platzieren (einen 1d-Vektor zu verwenden, um eine 2d-Eins mit Reihen-Großordnung darzustellen), um sie als Matrix zu verwenden. Ich benutze eine Struktur, die das Gewicht der Kante verfolgt, eine boolesche für ob es unendlich ist (keine Kante existiert) und eine Variable, um den vorhergehenden Knoten zu verfolgen.

Was mich ratlos ist, implementiert tatsächlich den Dang-Algorithmus. Ich habe den Pseudocode von http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm gelesen, aber ich habe eine schwierige Zeit zu begreifen, wie man den Algorithmus verwendet. Die ersten 80 Zeilen lesen die Datei ein, initialisieren den Vektor und werfen die Werte an der richtigen Stelle in den Vektor. Darunter habe ich angefangen, den Algorithmus zu implementieren. Ich habe ein paar spezifische Fragen.

1) In allen Erklärungen des Algorithmus, den ich gefunden habe, arbeiten Sie den Algorithmus Anzahl der Knoten - 1 mal. In einigen Implementierungen, die ich gesehen habe, tendiere ich dazu, bei 1 zu beginnen. Warum ist das? Und macht das mit meiner Implementierung noch Sinn?

2) Weiter im Wikipedia Pseudocode, es wird gesagt, um jede Kante u, v zu überprüfen, wobei u der Startknoten und v der Endknoten ist. In meiner Matrix müsste ich, soweit ich das verstehen kann, das Gewicht/den Wert jeder Zeile, jedes Spaltenpaars überprüfen und sehen, ob es einen besseren Pfad gibt. Ich bin ... nicht sicher, ob ich das richtig erkläre oder es sogar als diesen Punkt verstehe. Jede Beratung/Anleitung/Hinweise/Demonstrationen würde sehr geschätzt werden. Der Quellcode gefolgt von einer Paste der Demo-Eingabe des Instruktors ist unten.

#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]) 
} 

Demo-Eingang:

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

Für # 1, Sie sind die Kanten zwischen den Knoten untersuchen, so dass der längste Weg nicht mehr als nodeCount-1 Kanten sein. Wenn z. B. nodeCount == 1 ist, müssen keine Kanten untersucht werden.

Für # 2 haben Sie interessante Datenstrukturen. Es scheint, dass Sie andere brauchen. Ihr 'graphNode' sollte als 'graphEdge' ohne die 'pred' Variable bezeichnet werden. Deklarieren Sie zwei neue Strukturen:

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

Jeder hat die Größe nodeCount. Das 'w', das Sie in Wikipedia sehen, ist Ihre EdgeList.

Im letzten Abschnitt, den Sie auskommentiert haben, wiederholt die äußere Schleife nodeCount mal. Es sollte nodeCount-1 sein, aber kein Schaden. Ihre Indexierung ist später deaktiviert, da Sie eine eindimensionale EdgeList haben, die Sie als zweidimensional behandeln. Sie können über edgeList [(r-1) * nodeCount + c] auf die richtige Kante zugreifen.

Nicht sicher, ob dies als eine Antwort zählt, aber es ist ein Anfang.

Answer 2

Schauen Sie sich hier die kurzen Videos zum Bellman-Ford-Algorithmus an. Ich denke, es kann Ihnen helfen, den Algorithmus besser zu verstehen: https://class.coursera.org/algo2-2012-001/lecture/preview

Grundsätzlich ist die Grundidee hinter Bellman-Ford ist dies:

Um einen kürzesten Weg zwischen zwei Knoten zu finden, sagen s und t, finden Sie iterativ die Der kürzeste Weg, um von s nach t zu gelangen, und in jeder folgenden Iteration erlaubt es dem Algorithmus, 1 mehr Kante im Pfad als in der vorherigen Iteration zu verwenden.

Bei einer bestimmten Iteration k, wo Sie nun dem Algorithmus erlauben höchstens k Kanten in einem Pfad zu verwenden, der kürzeste Weg zwischen s und t könnte entweder

1. verbessern, indem sie mit genau k Kanten oder
2. nehmen Sie den gleichen Wert wie gefunden von der vorherigen Iteration dh usea höchstens (k - 1) Kanten.

Somit wird in einer bestimmten Iteration k:

Lassen d [k] [t] sein, der Abstand von s zu einem Knoten t höchstens k Kanten verwendet wird. Dann gilt:

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 
} 

, wo der zweite Teil der min {..,} Obige Gleichung nur den kürzesten Weg zwischen s findet zu jedem Nachbar u der Endbestimmung t und fügen die Kosten der Kante c [u] [t] von 0 bis t zu bekommen, wodurch genau k Kanten benötigt werden.

Der Pseudo-Code sieht somit wie folgt:

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 ] } 

Zum Teil 1 Ihrer Frage zu beantworten, der Ansicht, dass die äußere Schleife der Gleichung über die Anzahl der Kanten Schleifen. Es steigt von 1 bis n - 1, wobei n die Anzahl der Knoten im Graphen ist. Der Grund dafür ist, dass die maximale Anzahl an Kanten, die Sie in einem Pfad haben können, (n - 1) Kanten ist (dh Sie verbinden alle n Knoten, um von s nach t zu kommen, mit n - 1 Kanten) zwischen ihnen).

Um Teil 2 Ihrer Frage zu beantworten, müssen Sie nur die eingehenden Knoten an jedem Zielknoten berücksichtigen und prüfen, ob ein Pfad zu einem dieser Knoten mit k - 1 Kanten PLUS die Kosten von diesem Knoten zu den Zielknoten kostet weniger als vorher, wie ich oben erklärt habe.

Zuletzt, um auf negativen Zyklus (der letzte Teil im Wiki-Code) zu überprüfen, führen Sie den Algorithmus für 1 weitere Iteration. Wir wissen, dass jeder Pfad höchstens n - 1 Kanten verwenden kann. Mehr wäre überflüssig. Wenn also die Kosten für einen Pfad sinken, wenn Sie die Verwendung von 1 weiteren Kanten erlauben, muss ein negativer Zyklus enthalten sein, da nur so die Kosten gesenkt werden können. Jeder nicht-negative Zyklus hätte zu denselben oder höheren Kosten geführt, da mehr Kanten verwendet wurden.

Ich empfehle ernsthaft, Tim Roughgardens Video im obigen Link zu sehen. Beachten Sie, dass seine Behandlung sich etwas vom Pseudocode in Wikipedia unterscheidet, aber die Idee ist im Wesentlichen die gleiche.