Первая строка входного файла для этой программы - целое число N, указывающее количество вершин исходного ориентированного графа на N изолированных вершинах. Каждая последующая строка состоит из трех чисел, указывающих ребро и его вес. Линия вида
uvw
указывает ребро от вершины u до вершины v веса w. Все веса ребер неотрицательны. После считывания количества вершин расстояния всех вершин от вершины 1 (источника) инициализируются, как это обычно делается с помощью алгоритмов релаксации. По мере чтения каждого ребра расстояния, на которые влияет добавление ребра к графику, обновляются. Это повторяется до тех пор, пока не будут считаны все ребра. Назовите ребро полезным, если его добавление к графику вызывает изменение расстояний. Следите за количеством полезных ребер.
В вашей программе вы должны реализовать описанный выше процесс двумя способами, причем каждый способ реализован как одна функция: BF или BFS. В BF вы просто используете стратегию Беллмана-Форда, заключающуюся в повторении фаз до тех пор, пока расстояния продолжают изменяться, когда на каждой фазе вы сканируете все края в поисках релаксаций. В BFS вы используете подход поиска в ширину и отслеживаете вершины, которые изменяют расстояния в очереди Q, и обновляете затронутые расстояния, реализуя следующую стратегию: многократно извлекайте вершину u из Q и ослабляйте все ее исходящие ребра втекущий график и добавьте всех соседей, чьи расстояния были изменены в очередь (если их еще нет в очереди). Продолжайте так до тех пор, пока очередь не станет пустой.
Я провел исследование алгоритма Беллмана Форда, и все реализации, которые я видел, включают создание массива ребер, но я думаю, что это было бы неправильно для этой реализации, однако яне знаю, прав ли я
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest, int wt);
void printGraph(struct Graph* graph);
void squareGraph(struct Graph* graph);
struct node* createNode(int);
struct node
{
int vertex; //This will be our color 0 for white and 1 for black
struct node* next;
struct node* prev;
int weight;
};
struct Graph
{
int numVertices;
};
struct node* createNode(int v)
{
struct node* newNode = malloc(sizeof(struct node)); // allocate memory based on the size of stuct node when it is created
newNode->vertex = v; // node vertex = v
newNode->next = NULL; // node next value is none existant
return newNode; // returns the created node
}
Окончательный результат программы состоит из одной строки из трех чисел: первое число - количество полезных ребер, второе число - количество вызовов функции RELAX вBF, а третье число - это количество вызовов функции RELAX в BFS.