У меня есть ориентированный граф с около 10000 узлов. Все ребра взвешены. Я хочу найти отрицательный цикл, содержащий только 3 ребра. Есть ли алгоритм быстрее, чем O (n ^ 3)?
пример кода: (г мой график)
if (DETAILS) std::printf ("Calculating cycle of length 3.\n");
for (int i=0;i<NObjects;i++)
{
for (int j=i+1;j<NObjects;j++)
{
for (int k=j+1;k<NObjects;k++)
{
if ((d= g[i][j]+g[j][k]+g[k][i])<0)
{
results[count][0] = i;
results[count][1] = j;
results[count][2] = k;
results[count][3] = d;
count++;
if (count>=MAX_OUTPUT_SIZE3)
goto finish3;
}
if ((d= g[i][k]+g[k][j]+g[j][i])<0)
{
results[count][0] = j;
results[count][1] = i;
results[count][2] = k;
results[count][3] = d;
count++;
if (count>=MAX_OUTPUT_SIZE3)
goto finish3;
}
}
}
}
finish3:
Я не могу придумать ни одного алгоритма с определенной сложностью ниже, чем O (n3), но также постоянный фактор важен на практике. Следующий алгоритм позволяет сократить время нахождения цикла длиной 3 с отрицательной суммой весов — или проверить, что такого цикла нет.
Идея состоит в том, что хотя бы один из ребер цилиндра с отрицательной суммой должен иметь отрицательный вес. И что мы можем начать цикл с края с наименьшим весом в цикле.
Если вы знаете, что число ребер с отрицательными весами равно O (n), то этот алгоритм будет O (n).2 ld n), поскольку в этом случае в алгоритме будет доминировать шаг 1 (= сортировка ребер по их весу).
Других решений пока нет …