Двунаправленная реализация алгоритма Дейкстры в переполнении стека

Недавно я только начал изучать c ++, и для моего следующего домашнего задания я должен реализовать двунаправленную версию алгоритма Дейкстры. Я должен основываться на моем последнем назначении, которое создает график с использованием векторов. Мне интересно, как лучше настроить это назначение, используя мой код. Вот фактическое назначение:


Машинная задача 3: алгоритм двунаправленного кратчайшего пути: Ира Пол, 24 января 2014 г.

Цель: улучшить класс графика и добавить алгоритм Дейкстры и двунаправленного текста

Графовые алгоритмы и графическое представление — критический инструмент в CS. Основная проблема будет состоять в том, чтобы написать алгоритм Дейкстры как функцию-член класса (метод в ОО говорит). Вы уже должны знать алгоритм Дейкстры для задачи кратчайшего пути из предыдущего опыта, но он будет рассмотрен в классе. Это основа для многих программ расчета и оптимизации маршрутов.

Для графиков используются две основные реализации: одна — это краевые списки, а другая — матрицы связности. Вы можете решить, что использовать, но прокомментируйте свой выбор.

Основная проблема: напишите набор конструкторов для объявления и инициализации графа или используйте вашу предыдущую реализацию графа. У края будет положительная стоимость, которая является его расстоянием. Иметь процедуру, которая может для графа размером не менее 1000 создать случайно сгенерированный набор ребер с положительными расстояниями. Предположим, что графики не являются ориентированными. Процедура случайного графа должна иметь граничную плотность в качестве параметра и диапазон расстояний в качестве параметра. Таким образом, график, плотность которого равна 0,1, будет иметь 10% его ребер, выбранных случайным образом, а расстояние до его ребер будет выбрано случайным образом из диапазона расстояний. Это, конечно, уже было разработано в проблеме 2.

Двунаправленный алгоритм Дейкстры должен повторно использовать код из однонаправленного алгоритма Дейкстры.


#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cmath>

double probability(){ return 1.0*rand()/RAND_MAX;}using namespace std;
//class that has make_graph as constructor
class Graph{
public:
Graph(int s, double density);
void print_graph();
private:
int size;
vector<vector<bool> > g1; //A vector of vectors of bools
//Think of a vector as a first in, last out Data Structure
};//make_graph altered to work in c++
Graph::Graph(int s, double density){
this->size = s;
for (int i = 0; i < s; ++i){
// We push a new vector of bool onto the initial vector s times
// The * is there to dereference the new vector that we insert
this->g1.push_back( *( new vector<bool>() ) );
for (int j = 0; j < s; ++j){
//then, on each of those vectors, we push a default "false" s times
this->g1.at(i).push_back(false);
}
}
//Don't have to change this part much
for (int i = 0; i < s; ++i){
for (int j = 0; j < s; ++j){
if (probability()< density) this->g1[i][j] = true;
}
}
}

//simple conversion, just needed 'this'
void Graph::print_graph(){
cout << "graph size " << this->size << "\n";
for(int i = 0; i < this->size; ++i){
for (int j = 0; j < this->size; ++j){
cout << this->g1[i][j] << "\t";
}
cout << "\n";
}
}

int main(){
srand(time(0));
cout << "Test simple graph generation\n";
Graph* test1 = new Graph(10, 0.7);
test1->print_graph();
cout << "\nEND of TEST 1\n\n";
Graph* test2 = new Graph(8, 0.5);
test2->print_graph();
cout << "\nEND of TEST 2\n\n";
return 0;
}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …