Я изучаю C ++, и у меня проблема с алгоритмом Дейкстры, чтобы он находился точно на среднем кратчайшем пути. Более того, я генерирую график случайным образом, используя плотность. Это мой код, но я не знаю, где я допустил ошибку. Вывод среднего расстояния всегда nan. Как это исправить я не могу найти ошибку? Пожалуйста, помогите мне
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <ctime>
#include <random>
#include <tuple>
#include <limits>
using namespace std;
class Dijkstra {
private:
int node, edge;
vector<int> parent;
vector<int> dist;
vector<vector<pair<int, int>>> adj;
public:
Dijkstra() {}
Dijkstra(int node, int edge);
void add(int u, int v, int w);
void fnd(int start);
void print(int x);
bool trfl();
int N() {
return node;
}
void printvec() {
for(int i=0; i<adj.size(); i++) {
for(int j=0; j<adj[i].size(); j++) {
cout << adj[i][j].first << ", " << adj[i][j].second;
}
cout << endl;
}
}
vector<int> getDist() {
return dist;
}
vector<vector<pair<int, int>>> getAdj() {
return adj;
}
};
Dijkstra::Dijkstra(int node, int edge) : node(node), edge(edge) {
vector<int>(node+1).swap(parent);
vector<int>(node+1, numeric_limits<int>::max()).swap(dist);
vector<vector<pair<int, int>>>(node+1).swap(adj);
}
void Dijkstra::add(int u, int v, int w) {
if(w < 0) {
throw invalid_argument("Weight of an edge can not be negative!");
}
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
void Dijkstra::fnd(int start) {
parent[start] = -1;
dist[start] = 0;
set<pair<int, int>> s {{0, start}};
while(!s.empty()) {
auto it = *s.begin();
auto cur_node = it.second;
auto cur_level = it.first;
s.erase(s.begin());
for(auto u : adj[cur_node]) {
if(dist[u.first] - u.second > cur_level) {
dist[u.first] = cur_level + u.second;
parent[u.first] = cur_node;
//Q.push({dist[u.first], u.first});
s.insert({dist[u.first], u.first});
}
}
}
}
void Dijkstra::print(int x) {
if(dist[x] == numeric_limits<int>::max()) { cout << "-1" << endl; return; }
if (x == -1) { return; }
print(parent[x]);
cout << x << " ";
}
class ShortestPath {
private:
Dijkstra g_;
vector<int> dist_;
unsigned int source_;
int num;
vector<int> parent;
public:
ShortestPath(Dijkstra g, int num, unsigned int source = 0):
g_(g),
num(num),
dist_(num, numeric_limits<double>::max()),
source_(source) {
compute(source_);
}
double operator[](int idx) const {
return dist_[idx];
}
void compute(int source) {
set<pair<int, int>> s {{0, source}};
while(!s.empty()) {
auto it = *s.begin();
auto cur_node = it.second;
auto cur_level = it.first;
s.erase(s.begin());
for(auto u : g_.getAdj()[cur_node]) {
if(dist_[u.first] - u.second > cur_level) {
dist_[u.first] = cur_level + u.second;
parent[u.first] = cur_node;
s.insert({dist_[u.first], u.first});
}
}
}
}
};
class Runner {
private:
double avg_;
int num_;
double den_;
mt19937 random_generator_;
uniform_real_distribution<double> distance_distribution_;
uniform_real_distribution<double> existence_distribution_;
public:
Runner(int num = 50, double density = 0.2,
double distance_min = 1, double distance_max = 10,
int times = 50):
num_(num),
den_(density),
random_generator_(time(NULL)),
distance_distribution_(distance_min, distance_max),
existence_distribution_(0.0, 1.0) {
double sum_avg_dist = 0;
for (int i = 0; i < times; i++) {
sum_avg_dist += run_simulation();
}
avg_ = sum_avg_dist / times;
}
double average_distance() const {
return avg_;
}
protected:
double run_simulation() {
Dijkstra g = generate_graph();
ShortestPath sp(g, num_, 0);
int count = 0;
double sum = 0;
for (int i = 1; i < num_; i++) {
if (sp[i] < numeric_limits<double>::max()) {
//cout << "LL" << "\n";
count++;
sum += sp[i];
}
}
cout << "AAA " << sum << " " << count << "\n";
return sum / count;
}
Dijkstra generate_graph() {
Dijkstra g(num_, num_);
for (int i = 0; i < num_ - 1; i++) {
for (int j = i + 1; j < num_; j++) {
if (existence_distribution_(random_generator_) < den_) {
g.add(i, j, distance_distribution_(random_generator_));
}
}
}
return g;
}
};
int main() {
Dijkstra d(5, 6);
d.add(1,2,2);
d.add(2,5,5);
d.add(2,3,4);
d.add(1,4,1);
d.add(4,3,3);
d.add(3,5,1);
d.fnd(1);
d.print(5);
Runner rn;
cout << rn.average_distance() << "\n";
}