- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
#define __DEBUG
#ifdef __DEBUG
#define print_pair(p) do{std::cout << "(" << ((p).first + 1) << ", "\
<< ((p).second + 1) << ")" << std::endl;}while(0);
#endif
Graph::result
Graph::dijkstra (int start)
{
#ifdef __DEBUG
std::cout << "Dijkstra algorithm tracing:" << std::endl;
#endif
distances[start] = 0;
std::set<std::pair<int, int>> q;
q.insert (std::make_pair(distances[start], start));
while (!q.empty())
{
#ifdef __DEBUG
std::cout << "top element of a set: ";
print_pair(*q.begin());
#endif
int current = q.begin()->second;
q.erase(q.begin());
for (int i = 0; i < adj[current].size(); ++i)
{
#ifdef __DEBUG
std::cout << "current vertex: " << (current + 1);
std::cout << " ad current state of distances array is: " << std::endl;
for (auto i: distances)
std::cout << i << " ";
std::cout << std::endl;
#endif
int to = adj[current][i].second;
int length = adj[current][i].first;
// Relaxations
if (distances[to] > distances[current] + length)
{
#ifdef __DEBUG
std::cout << "relaxation for edge (" << current << ", " << to << ") ";
std::cout << "with weight " << length << std::endl;
#endif
q.erase(std::make_pair(distances[to], to));
distances[to] = distances[current] + length;
path[to] = current;
q.insert(std::make_pair(distances[to], to));
}
}
}
// Replace INF by -1
std::replace (distances.begin(), distances.end(), INF, -1);
return distances;
}
Я у мамы решил подебажить как мыщъх дебажил при помощи отладочной печати. Вот что получилось.
Follow us!