0
Я работаю над программой, чтобы получить базовые знания о том, как работает поиск путей, и решил использовать Алгоритм Дейкстры, чтобы найти кратчайшее расстояние между двумя точками 2D-массива которые пользователь выбирает. Я использовал класс Graph с тремя методами: один для чтения, печати и кратчайший. Однако я не знаю, как сделать алгоритм для программы, которую я создал. Любая помощь будет оценена!Алгоритм Дейкстры, находящий кратчайшее расстояние между двумя вершинами C++
Программа считывает эти значения, при этом первая устанавливается на переменную с именем size, а остальная часть вводится в 2D-массив, называемый расстоянием.
4
0 1.7 0.3 0
1.7 0 0.1 3.6
0.3 0.1 0 0
0 3.6 0 0
Это мой Graph.h файл:
class Graph
{
public:
void read(const char* filename);
void print(ostream& out);
float shortest(int v1, int v2);
private:
int size;
float max_edge_length;
float distance[MAX_VERTICES][MAX_VERTICES];
};
Ниже мое начало на создание методов чтения и печати.
void Graph::read(const char* filename){
int x, y;
ifstream myfile(filename);
if (myfile.good()){
myfile >> size;
for (y = 0; y < size; y++){
for (x = 0; x < size; x++){
myfile >> distance[x][y];
}
}
}
}
void Graph::print(ostream& out){
out << size << endl;
for (int y = 0; y < size; y++){
for (int x = 0; x < size; x++){
out << distance[x][y] << " ";
}
out << endl;
}
}
float Graph::shortest(int v1, int v2){
}
Вторая структура данных, что необходимо для первопрохождения (после графа) является приоритетной очереди. Можете ли вы реализовать эффективную шаблонную очередь приоритетов? Можете ли вы построить один из существующих стандартных частей библиотеки? Что делать, если вам нужно было строить свои собственные с нуля; как бы вы это сделали? –
Вы просите нас предоставить вам реализацию алгоритма Дейкстры? Это может быть немного не по теме, есть множество обучающих программ на C++, какие источники вы проверили перед публикацией здесь и что вы пытались реализовать до сих пор? – Zimano