Привет, я хотел решить проблему «кратчайшего цикла через заданный край», которая есть на этом веб-сайте http://rosalind.info/problems/cte/. Предположим, что наше конкретное ребро (то есть наше первое ребро в этой проблеме) будет 'E'. Я написал программу для решения этой проблемы, и мой алгоритм состоит в том, чтобы использовать DFS на end_node из 'E', и это продолжается до встречи start_node из 'E'. он отлично работает для образца, приведенного на этом веб-сайте, но когда я использовал большие данные, он переходит в цикл. Я пробовал много примеров простых ориентированных графов и не понял, почему они зацикливаются. может ли кто-нибудь показать мне, есть ли так или иначе, что он зацикливается?
вот моя программа:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stack>
using namespace std;
#define ll long long int
#define pb push_back
#define mk make_pair
const ll maxn = 1e5 + 3;
const ll inf = 1e12 + 10;
vector <ll> cost;
void is_cyclic(int i, bool * recstack,ll cnt,vector <pair<ll,ll>> * vec,ll ind) {
recstack[i] = true;
vector <pair<ll, ll>>::iterator it = vec[i].begin();
for (; it != vec[i].end(); it++) {
if (it->first == ind) {
cnt += it->second;
cost.pb(cnt);
}
else {
if (recstack[it->first] == false) {
is_cyclic(it->first, recstack, cnt + it->second, vec, ind);
}
}
}
recstack[i] = false;
}
int main() {
ll k;
//file >> k;
//while (k--) {
ll n, m;
cin >> n >> m;
ll s;
vector <pair<ll, ll>> * vec;
vec = new vector<pair<ll, ll>>[n];
for (int j = 0; j < m; j++) {
ll a, b, c;
cin >> a >> b >> c;
if (j == 0) {
s = a - 1;
}
vec[a - 1].pb(mk(b - 1, c));
}
bool * recstack = new bool[n];
for (int j = 0; j < n; j++) {
recstack[j] = false;
}
ll cnt = 0;
pair <ll, ll> p;
p = vec[s][0];
cnt += p.second;
recstack[s] = true;
is_cyclic(p.first, recstack, cnt, vec,s);
if (cost.size() == 0) {
cout << -1 << " ";
}
else {
sort(cost.begin(), cost.end());
cout << cost[0] << " ";
}
cost.clear();
//}
return 0;
}
Во-первых, вы должны использовать BFS, а не DFS, для вычисления кратчайших путей в невзвешенных графах.
Во-вторых, практически невозможно точно понять, как работает ваш код. Если вы хотите получить содержательные ответы, я бы рекомендовал очистить ваш код. Вот несколько указателей:
std::vector<…> vec
, делают ваш код очень трудным для понимания.#define pb push_back
. Это делает практически невозможным чтение вашего кода для всех, кто не является вами.delete
). Примеры: vec
или recstack
(сделайте это std::vector<bool>
…)std::numeric_limits
вместо определения вашего собственного maxn
и т. д..push_back(std::make_pair(a,b))
используйте .emplace_back(a,b)