How do I find the least cycle of an unguided graph?

However, since the finding of the shortest path is a complete NP problem, the solutions are inefficient, or even mathematically incalculable in numbers, not so large. If I'm not mistaken for targeted graphs I used the algorithm of Floyd-Warshall Floyd-Warshall .

First of all, you should give weight 1 to all existing edges of your graph and weight INFINITO to edges grafo[i][i] to every vertex i . Also make your pseudo-directed graph:

grafo[i][j] = 1
grafo[j][i] = 1

for any vertices i and j that are connected.

Generally, the weight at the grafo[i][i] edge is 0 , which makes sense when you look for the shorter path , since it does not cost anything does not move in the graph , but if you keep that way and run the algorithms below, your final result will be only 0 , since the smallest cycle from a vertex to itself will always be the path vertex i - > vertex i , that is, do not move in the graph .

That said, you can run the Dijkstra Algorithm for every vertex i , using i as the verifying that the answer is not going to be i because you have defined that the% and% vertex of the algorithm, ie, how much it costs to get to the vertex i from the vertex itself 0 grafo[i][i] = INFINITO ). And because the weights of the edges are all 1 , the shortest path will also give you the shortest distance loop. Running this algorithm for all vertices you will have grafo[i][i] going to be the cost of the shortest cycle in which the i vertex is involved, for every vertex i . Final complexity O (n ^ 3) :

Dijkstra: O(n^2)
Executado n vezes, onde n é a quantidade de vértices no grafo.
Final: O(n^2) * n --> O(n^3)

To find the smallest cycle in the entire graph, run the above algorithm and then get min(grafo[i][i]) for every vertex i , that is: taking all the cycles in which the vertices are involved, which one is the smallest ?!