Aqui está um imposto:

Seja G um grafo direcionado ponderado com n vértices e m arestas, onde todas as arestas têm peso positivo. Um ciclo direcionado é um caminho direcionado que inicia e termina no mesmo vértice e contém pelo menos uma borda. Dê um algoritmo O (n ^ 3) para encontrar um ciclo dirigido em G de peso total mínimo. Crédito parcial será dado para um algoritmo O ((n ^ 2) * m).

Aqui está meu algoritmo.

Eu faço umDFS. Cada vez que encontro umback edgeEu sei que tenho um ciclo dirigido.

Então eu vou temporariamente para trás ao longo doparent array (até eu viajar por todos os vértices do ciclo) e calcular ototal weights.

Então eu comparo ototal weight deste ciclo commin. min sempre leva o peso total mínimo. Após o DFS terminar, nosso ciclo mínimo dirigido também é encontrado.

Ok, então sobre a complexidade do tempo.

Para ser honesto, não conheço a complexidade de tempo do meu algoritmo.

Para o DFS, o percurso leva O (m + n) (se m é o número de arestas e n é o número de vértices). Para cada vértice, ele pode apontar para um de seus ancestrais e, assim, formar um ciclo. Quando um ciclo é encontrado, é preciso O (n) para resumir os pesos totais.

Então eu acho que o tempo total é O (m + n * n). Mas obviamente está errado, como dito no imposto especial de consumo, o tempo ótimo é O (n ^ 3) e o tempo normal é O (m * n ^ 2).

Alguém pode me ajudar com:

Meu algoritmo está correto?Qual é a complexidade de tempo se meu algoritmo estiver correto?Existe algum algoritmo melhor para esse problema?