Как я могу найти отрицательный взвешенный цикл из 3 ребер в графе?
У меня есть ориентированный граф с около 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 с отрицательной суммой весов — или проверить, что такого цикла нет.
- сортировать (направленные) края в соответствии с их весом
- возьмите край с наименьшим весом в качестве начального края.
- попробуйте все ребра, соединенные с конечной вершиной начального ребра, с весом не ниже начального ребра (1-я обрезка) и проверьте сумму весов при закрытии цикла. Если вы нашли цикл с отрицательной суммой, все готово.
- продолжайте с ребром со следующим наименьшим весом в качестве начального ребра. Если его вес отрицателен, переходите к 3 — в противном случае вы закончили (2-я обрезка)
Идея состоит в том, что хотя бы один из ребер цилиндра с отрицательной суммой должен иметь отрицательный вес. И что мы можем начать цикл с края с наименьшим весом в цикле.
Если вы знаете, что число ребер с отрицательными весами равно O (n), то этот алгоритм будет O (n).2 ld n), поскольку в этом случае в алгоритме будет доминировать шаг 1 (= сортировка ребер по их весу).
Другие решения
Других решений пока нет …
detector