В настоящее время я работаю над домашним заданием по реализации алгоритма Bellman-Ford. До сих пор мне удалось прочитать на представленном графике, поместить его в вектор (использование 1D-вектора для представления 2D с порядок строк мажор) для использования в качестве матрицы. Я использую структуру, которая отслеживает вес края, логин для того, является ли это бесконечностью (нет края) и переменная, чтобы отслеживать узел предыдущего оборота. Я прочитал псевдокод с http://en.wikipedia.org/wiki/bellman%E2 ... _algorithm, но мне трудно понять, как использовать алгоритм. Первые 80 строк читают в файле, инициализация вектора, бросая значения в вектор в нужном месте. Ниже это то, что я начал реализовывать для алгоритма. У меня есть несколько конкретных вопросов. В некоторых из реализаций этого, на которые я смотрел, я, как правило, начинаю с 1. Почему это? Кроме того, с моей реализацией, это все еще имеет смысл? В моей матрице, насколько я понимаю, это будет означать, что мне нужно проверить вес/значение каждой строки, пара столбцов и посмотреть, есть ли лучший путь. Я ... не уверен, что я объясняю это правильно или даже понимаю это как этот момент. Любые советы/рекомендации/подсказки/демонстрации будут высоко оценены. Исходный код, за которым следует вставка демонстрационного ввода инструктора ниже. < /P>
#include
#include
#include
#include
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/7651 ... 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 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 > 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.value = infinity;
edgeList.isInfinity = true;
edgeList.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
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
Подробнее здесь: https://stackoverflow.com/questions/160 ... lgorithm-c
